#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n, K, maxx;
int dx[2] = {1, 0}, dy[2] = {0, 1};
int ans[maxn << 1];
int a[maxn][maxn], f[maxn][maxn];
bool vis[maxn][maxn];
char s[maxn];
struct node {
  int x, y, step;
};
inline void bfs() {
  queue<node> q;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (f[i][j] == K && i + j - 1 == maxx)
        q.push((node){i, j, maxx}), vis[i][j] = 1;
  if (q.empty()) q.push((node){1, 1, 1}), ans[1] = a[1][1];
  while (!q.empty()) {
    node now = q.front();
    q.pop();
    if (a[now.x][now.y] > ans[now.step]) continue;
    for (int i = 0; i < 2; i++) {
      int mx = now.x + dx[i], my = now.y + dy[i];
      if (mx > n || my > n || ans[now.step + 1] < a[mx][my] || vis[mx][my])
        continue;
      vis[mx][my] = 1;
      ans[now.step + 1] = a[mx][my];
      q.push((node){mx, my, now.step + 1});
    }
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1; j <= n; j++) a[i][j] = s[j] - 'a';
  }
  memset(ans, 0x3f, sizeof(ans));
  memset(f, 0x3f, sizeof(f));
  f[0][1] = f[1][0] = 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] == 0 ? 0 : 1);
      if (f[i][j] == K && maxx < i + j - 1) maxx = i + j - 1;
    }
  bfs();
  if (f[n][n] < K) {
    for (int i = 1; i < 2 * n; i++) printf("a");
    return 0;
  }
  for (int i = 1; i <= maxx; i++) printf("a");
  for (int i = maxx + 1; i < 2 * n; i++) printf("%c", ans[i] + 'a');
  return 0;
}
