#include <bits/stdc++.h>
using namespace std;
int n, k;
int f[3001][3001], vis[3001][3001];
char s[3001][3001];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  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]);
      if (s[i][j] != 'a') f[i][j]++;
    }
  int max0 = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (f[i][j] <= k) max0 = max(max0, i + j);
  for (int i = 2; i <= max0; i++) putchar('a');
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i + j == max0 && f[i][j] <= k) vis[i][j] = 1;
  if (max0 == 1) vis[0][1] = vis[1][0] = 1;
  for (int kx = max0 + 1; kx <= n * 2; kx++) {
    for (int i = 1; i < kx; i++)
      if (i <= n && kx - i <= n)
        vis[i][kx - i] = vis[i - 1][kx - i] | vis[i][kx - i - 1];
    char minc = 'z';
    for (int i = 1; i < kx; i++)
      if (i <= n && kx - i <= n && vis[i][kx - i])
        minc = min(minc, s[i][kx - i]);
    for (int i = 1; i < kx; i++)
      if (i <= n && kx - i <= n && s[i][kx - i] != minc) vis[i][kx - i] = 0;
    putchar(minc);
  }
  putchar('\n');
  return 0;
}
