#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int maxn = 2050;
char s[maxn][maxn];
char ans[maxn * 2];
int da[maxn][maxn], dis[maxn][maxn];
const int inf = 0x3f;
struct node {
  int x, y;
};
queue<node> q;
int xi[2] = {0, 1};
int yi[2] = {1, 0};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  dis[1][1] = 1;
  da[1][1] = (s[1][1] == 'a');
  for (int i = 1; i < 2 * n; i++) ans[i] = 'z';
  ans[1] = (s[1][1] == 'a' || m > 0) ? 'a' : s[1][1];
  dis[1][1] = 1, da[1][1] = (s[1][1] == 'a');
  ans[2 * n] = '\0';
  node now;
  now.x = 1;
  now.y = 1;
  q.push(now);
  while (!q.empty()) {
    node fi = q.front();
    q.pop();
    int pos = fi.x + fi.y - 1;
    if (dis[fi.x][fi.y] - da[fi.x][fi.y] > m && s[fi.x][fi.y] > ans[pos])
      continue;
    for (int i = 0; i < 2; i++) {
      int dx = fi.x + xi[i];
      int dy = fi.y + yi[i];
      if (dx < 1 || dx > n || dy < 1 || dy > n) continue;
      int flag =
          (s[dx][dy] == 'a') && ((dis[fi.x][fi.y] - da[fi.x][fi.y]) <= m);
      if (dis[dx][dy] == 0) {
        dis[dx][dy] = dis[fi.x][fi.y] + 1;
        da[dx][dy] = da[fi.x][fi.y] + flag;
        now.x = dx;
        now.y = dy;
        q.push(now);
        ans[pos + 1] = min(ans[pos + 1],
                           (dis[dx][dy] - da[dx][dy] <= m) ? 'a' : s[dx][dy]);
      } else if (da[dx][dy] < da[fi.x][fi.y] + flag) {
        da[dx][dy] = da[fi.x][fi.y] + flag;
        ans[pos + 1] = min(ans[pos + 1],
                           (dis[dx][dy] - da[dx][dy] <= m) ? 'a' : s[dx][dy]);
      } else
        ans[pos + 1] = min(ans[pos + 1], s[dx][dy]);
    }
  }
  printf("%s\n", ans + 1);
  return 0;
}
