#include <bits/stdc++.h>
using namespace std;
const int maxn = 2050;
char a[maxn][maxn];
bool vis[maxn][maxn];
struct node {
  int from, use, x, y;
  char c;
};
node dp[maxn * 2];
bool cmp(node& fuck1, node& fuck2) {
  if (fuck1.c == fuck2.c) {
    if (fuck1.use >= fuck2.use) return true;
    return false;
  }
  if (fuck1.c < fuck2.c) return true;
  return false;
}
bool check(node& fuck1, node& fuck2) {
  if (fuck1.c <= fuck2.c) return true;
  return false;
}
int n;
bool checkxy(int x, int y) {
  if (x > 0 && x <= n && y > 0 && y <= n) return true;
  return false;
}
node ans[maxn][maxn];
vector<node> fuck;
void output(int x, int y) {
  if (x == 1 && y == 1) {
    printf("%c", ans[x][y].c);
    return;
  }
  int j = ans[x][y].from;
  output(fuck[j].x, fuck[j].y);
  printf("%c", ans[x][y].c);
}
vector<node> canmove;
int main() {
  int i, j, m, k, p, sn, last_move;
  while (scanf("%lld%lld", &n, &k) != EOF) {
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) scanf(" %c", &a[i][j]);
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) ans[i][j].c = '}';
    node tmp;
    tmp.from = -1;
    tmp.x = 1;
    tmp.y = 1;
    tmp.use = k;
    memset(vis, false, sizeof(vis));
    if (a[1][1] != 'a') {
      if (tmp.use > 0) {
        tmp.use--;
        tmp.c = 'a';
      } else
        tmp.c = a[1][1];
    } else
      tmp.c = 'a';
    ans[1][1] = tmp;
    for (i = 1; i <= n + n; i++) dp[i].c = '}';
    fuck.clear();
    fuck.push_back(tmp);
    p = 0;
    sn = 0;
    last_move = 1;
    while (p <= sn) {
      tmp = fuck[p];
      int xd = tmp.x + 1, yd = tmp.y, xr = tmp.x, yr = tmp.y + 1;
      if (checkxy(xd, yd)) {
        node new_tmp;
        new_tmp.from = p;
        new_tmp.use = tmp.use;
        new_tmp.x = xd;
        new_tmp.y = yd;
        if (a[xd][yd] != 'a') {
          if (new_tmp.use > 0) {
            new_tmp.use--;
            new_tmp.c = 'a';
          } else
            new_tmp.c = a[xd][yd];
        } else
          new_tmp.c = 'a';
        if (check(new_tmp, dp[xd + yd - 1])) {
          dp[xd + yd - 1] = new_tmp;
          if (cmp(new_tmp, ans[new_tmp.x][new_tmp.y])) {
            ans[new_tmp.x][new_tmp.y] = new_tmp;
          }
          canmove.push_back(new_tmp);
        }
      }
      if (checkxy(xr, yr)) {
        node new_tmp;
        new_tmp.from = p;
        new_tmp.use = tmp.use;
        new_tmp.x = xr;
        new_tmp.y = yr;
        if (a[xr][yr] != 'a') {
          if (new_tmp.use > 0) {
            new_tmp.use--;
            new_tmp.c = 'a';
          } else
            new_tmp.c = a[xr][yr];
        } else
          new_tmp.c = 'a';
        if (check(new_tmp, dp[xr + yr - 1])) {
          dp[xr + yr - 1] = new_tmp;
          if (cmp(new_tmp, ans[new_tmp.x][new_tmp.y])) {
            ans[new_tmp.x][new_tmp.y] = new_tmp;
          }
          canmove.push_back(new_tmp);
        }
      }
      p++;
      if (p > sn) {
        for (int i = 0; i < canmove.size(); i++) {
          node tmp = canmove[i];
          if (check(tmp, dp[tmp.x + tmp.y - 1]) &&
              cmp(tmp, ans[tmp.x][tmp.y]) && !vis[tmp.x][tmp.y]) {
            sn++;
            fuck.push_back(tmp);
            vis[tmp.x][tmp.y] = true;
          }
        }
        canmove.clear();
      }
    }
    output(n, n);
    printf("\n");
  }
}
