#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
char getc() {
  char ch = getchar();
  while (ch > 'z' || ch < 'a') ch = getchar();
  return ch;
}
char c[N][N];
int f[N][N], pre[N][N];
int b[N][N];
char ans[2 * N + 10];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) c[i][j] = getc();
  int minf = 1;
  for (int i = 0; i <= n; ++i) f[0][i] = f[i][0] = 3 * n;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (i == 1 && j == 1) {
        f[i][j] = c[i][j] != 'a';
        if (f[i][j] <= k) minf = max(minf, i + j);
        continue;
      }
      if (f[i - 1][j] < f[i][j - 1])
        f[i][j] = f[i - 1][j], pre[i][j] = 1;
      else
        f[i][j] = f[i][j - 1], pre[i][j] = 0;
      f[i][j] += (c[i][j] != 'a');
      if (f[i][j] <= k) minf = max(minf, i + j);
    }
  int X = n, Y = n;
  for (int j = max(1, minf - n); j <= n && j < minf; ++j) {
    if (f[j][minf - j] <= k) b[j][minf - j] = 1;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (i + j <= minf) c[i][j] = 'a';
  if (minf == 1) minf = 2, b[1][1] = 1;
  for (int i = minf; i < 2 * n; ++i) {
    char mn = 'z';
    for (int j = max(1, i - n); j <= n && j < i; ++j) {
      if (b[j][i - j] && j + 1 <= n) mn = min(mn, c[j + 1][i - j]);
      if (b[j][i - j] && i - j + 1 <= n) mn = min(mn, c[j][i - j + 1]);
    }
    for (int j = max(1, i - n); j <= n && j < i; ++j) {
      if (b[j][i - j] && j + 1 <= n && c[j + 1][i - j] == mn)
        b[j + 1][i - j] = 1, pre[j + 1][i - j] = 1;
      if (b[j][i - j] && i - j + 1 <= n && c[j][i - j + 1] == mn)
        b[j][i - j + 1] = 1, pre[j][i - j + 1] = 0;
    }
  }
  for (int i = 1; i <= 2 * n - 1; ++i) {
    ans[i] = c[X][Y];
    if (pre[X][Y])
      --X;
    else
      --Y;
  }
  for (int i = 2 * n - 1; i >= 1; --i) {
    putchar(ans[i]);
  }
}
