#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
string ha;
char a[maxn][maxn];
int f[maxn][maxn];
int n, m;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      char ch = getchar();
      while (!(ch <= 'z' && ch >= 'a')) ch = getchar();
      a[i][j] = ch;
    }
  if (m == 0) {
    ha = a[1][1];
    f[1][1] = 0;
  } else {
    ha = 'a';
    f[1][1] = (a[1][1] != 'a');
  }
  for (int _ = 2; _ <= 2 * n - 1; _++) {
    char c = 'z';
    for (int i = 1; i <= n; i++) {
      int j = _ + 1 - i;
      if (j <= 0 || j > n) continue;
      int k = -1;
      if (i > 1 && f[i - 1][j] != -1) {
        if (k == -1 || k > f[i - 1][j]) k = f[i - 1][j];
      }
      if (j > 1 && f[i][j - 1] != -1)
        if (k == -1 || k > f[i][j - 1]) k = f[i][j - 1];
      if (k == -1) {
        f[i][j] = -1;
        continue;
      }
      if (k < m)
        c = 'a';
      else
        c = min(c, a[i][j]);
    }
    for (int i = 1; i <= n; i++) {
      int j = _ + 1 - i;
      if (j <= 0 || j > n) continue;
      int k = -1;
      if (i > 1 && f[i - 1][j] != -1) {
        if (k == -1 || k > f[i - 1][j]) k = f[i - 1][j];
      }
      if (j > 1 && f[i][j - 1] != -1)
        if (k == -1 || k > f[i][j - 1]) k = f[i][j - 1];
      if (k == -1) {
        f[i][j] = -1;
        continue;
      }
      if (a[i][j] != c)
        f[i][j] = k + 1;
      else
        f[i][j] = k;
      if (f[i][j] > m) f[i][j] = -1;
    }
    ha += c;
  }
  printf("%s\n", ha.c_str());
  return 0;
}
