#include <bits/stdc++.h>
int a, b, i, j, m, p, q, sz, mini, v[2222][2222], x[2222][2222], D[2222][2222],
    X[] = {1, 0}, Y[] = {0, 1};
char s[2222];
int main() {
  scanf("%d%d", &a, &b);
  for (i = 1; i <= a; i++) {
    scanf("%s", s);
    for (j = 1; j <= a; j++) {
      x[i][j] = s[j - 1] - 'a';
    }
  }
  for (i = 1; i <= a; i++) {
    for (j = 1; j <= a; j++) {
      D[i][j] = std::max(D[i - 1][j], D[i][j - 1]);
      if (x[i][j] == 0) D[i][j]++;
    }
  }
  for (i = 1; i <= a; i++) {
    for (j = 1; j <= a; j++) {
      if (i + j - 1 - D[i][j] <= b) m = std::max(m, i + j - 1);
    }
  }
  for (i = 1; i <= m; i++) printf("a");
  for (i = 1; i <= a; i++) {
    j = m + 1 - i;
    if (1 <= j && j <= a && i + j - 1 - D[i][j] <= b) {
      v[i][j] = 1;
    }
  }
  if (m == 0) {
    m = 1;
    v[1][1] = 1;
    printf("%c", 'a' + x[1][1]);
  }
  for (int k = m; k < 2 * a - 1; k++) {
    mini = 30;
    for (i = 1; i <= a; i++) {
      j = k + 1 - i;
      if (1 <= j && j <= a && v[i][j] == 1) {
        if (i + 1 <= a) mini = std::min(mini, x[i + 1][j]);
        if (j + 1 <= a) mini = std::min(mini, x[i][j + 1]);
      }
    }
    printf("%c", mini + 'a');
    for (i = 1; i <= a; i++) {
      j = k + 1 - i;
      if (1 <= j && j <= a && v[i][j] == 1) {
        if (i + 1 <= a && mini == x[i + 1][j] && v[i + 1][j] == 0) {
          v[i + 1][j] = 1;
        }
        if (j + 1 <= a && mini == x[i][j + 1] && v[i][j + 1] == 0) {
          v[i][j + 1] = 1;
        }
      }
    }
  }
}
