#include <bits/stdc++.h>
using namespace std;
char s[2010][2010], ans[5010];
int f[2010][2010];
bool v[2010][2010];
int main() {
  int n, m, p = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  for (int i = 0; i <= n; i++) f[i][0] = f[0][i] = 0x3f3f3f3f;
  f[0][1] = 0;
  v[0][1] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      f[i][j] = min(f[i - 1][j], f[i][j - 1]) + !(s[i][j] == 'a');
      if (f[i][j] <= m) {
        p = max(i + j, p);
      }
    }
  for (int i = 2; i <= p; i++) ans[i] = 'a';
  for (int i = max(1, p - n); i < p && i <= n; i++) {
    if (f[i][p - i] <= m) v[i][p - i] = 1;
  }
  for (int k = p + 1; k <= 2 * n; k++) {
    ans[k] = 'z';
    for (int i = max(1, k - n); i <= n && i < k; i++) {
      int j = k - i;
      if (v[i - 1][j] || v[i][j - 1]) ans[k] = min(ans[k], s[i][j]);
    }
    for (int i = max(1, k - n); i <= n && i < k; i++) {
      int j = k - i;
      if ((v[i - 1][j] || v[i][j - 1]) && ans[k] == s[i][j]) v[i][j] = 1;
    }
  }
  printf("%s\n", ans + 2);
}
