#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, m, mx, top, ntop, f[N][N];
bool vis[N][N];
char a[N][N];
pair<int, int> q[N * N], nq[N * N];
bool chk(int x) { return 1 <= x && x <= n; }
void extend() {
  top = 0;
  for (int i = (1); i <= (ntop); i++) {
    int x = nq[i].first, y = nq[i].second;
    if (chk(x + 1) && chk(y) && !vis[x + 1][y])
      q[++top] = pair<int, int>(x + 1, y), vis[x + 1][y] = 1;
    if (chk(x) && chk(y + 1) && !vis[x][y + 1])
      q[++top] = pair<int, int>(x, y + 1), vis[x][y + 1] = 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); i++) scanf("%s", a[i] + 1);
  memset(f, 0x3f, sizeof(f));
  f[0][1] = 0;
  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]) + (a[i][j] != 97);
  mx = 0;
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (n); j++)
      if (f[i][j] <= m) mx = max(mx, i + j - 1);
  for (int i = (0); i <= (n); i++)
    for (int j = (1); j <= (n); j++)
      if (f[i][j] <= m && i + j - 1 == mx) nq[++ntop] = pair<int, int>(i, j);
  extend();
  m = mx;
  for (int i = (1); i <= (m); i++) putchar(97);
  for (int step = (m + 1); step <= (2 * n - 1); step++) {
    ntop = 0;
    char mi = 'z' + 1;
    for (int i = (1); i <= (top); i++)
      if (a[q[i].first][q[i].second] < mi)
        mi = a[q[i].first][q[i].second], nq[ntop = 1] = q[i];
      else if (a[q[i].first][q[i].second] == mi)
        nq[++ntop] = q[i];
    putchar(mi);
    if (step == 2 * n - 1) return 0;
    extend();
  }
  return 0;
}
