#include <bits/stdc++.h>
using namespace std;
void qmax(int &x, int y) {
  if (x < y) x = y;
}
void qmin(int &x, int y) {
  if (x > y) x = y;
}
inline long long read() {
  char s;
  long long k = 0, base = 1;
  while ((s = getchar()) != '-' && s != EOF && !(isdigit(s)))
    ;
  if (s == EOF) exit(0);
  if (s == '-') base = -1, s = getchar();
  while (isdigit(s)) {
    k = k * 10 + (s ^ '0');
    s = getchar();
  }
  return k * base;
}
inline void write(int x) {
  static char cnt, num[15];
  cnt = 0;
  if (!x) {
    printf("0");
    return;
  }
  for (; x; x /= 10) num[++cnt] = x % 10;
  for (; cnt; putchar(num[cnt--] + 48))
    ;
}
const int maxn = 2020;
int n, k;
char ch[maxn][maxn];
int a[maxn][maxn], Max;
char d[maxn + maxn];
bool vis[maxn][maxn];
int main() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", ch[i] + 1);
  }
  if (k >= (2 * n - 1)) {
    for (int i = 1; i <= n + n - 1; i++) putchar('a');
    return 0;
  }
  memset(a, 0x3f3f, sizeof(a));
  a[1][1] = 1;
  if (ch[1][1] == 'a') a[1][1] = 0;
  for (int l = 2; l <= n + n; l++) {
    for (int i = 1, j; i <= n; i++) {
      j = l - i;
      if (j <= 0) break;
      if (j > n) continue;
      if (i > n) continue;
      if (j + 1 <= n) qmin(a[i][j + 1], a[i][j] + (ch[i][j + 1] != 'a'));
      if (i + 1 <= n) qmin(a[i + 1][j], a[i][j] + (ch[i + 1][j] != 'a'));
      if (a[i][j] <= k) Max = max(Max, l);
    }
  }
  if (Max == n + n) {
    for (int i = 1; i <= n + n - 1; i++) putchar('a');
    return 0;
  }
  bool flag = false;
  if (!Max) Max = 2, vis[1][1] = true, d[2] = ch[1][1], flag = true;
  for (int i = 1, j; i <= n; i++) {
    j = Max - i;
    if (j <= 0) break;
    if (j > n) continue;
    if (a[i][j] <= k) vis[i][j] = true;
  }
  for (int l = Max; l <= n + n; l++) {
    char z = 'z';
    for (int i = 1, j; i <= n; i++) {
      j = l - i;
      if (j <= 0) break;
      if (j > n) continue;
      if (!vis[i][j]) continue;
      if (j + 1 <= n) z = min(z, ch[i][j + 1]);
      if (i + 1 <= n) z = min(z, ch[i + 1][j]);
    }
    d[l + 1] = z;
    for (int i = 1, j; i <= n; i++) {
      j = l - i;
      if (j <= 0) break;
      if (j > n) continue;
      if (!vis[i][j]) continue;
      if (j + 1 <= n && ch[i][j + 1] == z) vis[i][j + 1] = true;
      if (i + 1 <= n && ch[i + 1][j] == z) vis[i + 1][j] = true;
    }
  }
  if (flag) Max--;
  for (int i = 2; i <= Max; i++) d[i] = 'a';
  for (int i = 2; i <= n + n; i++) {
    putchar(d[i]);
  }
  return 0;
}
