#include <bits/stdc++.h>
namespace remoon {
inline int read() {
  int p = 0, w = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') p = p * 10 + c - '0', c = getchar();
  return p * w;
}
int wr[50], rw;
template <typename ra>
inline void write(ra o, char c = '\n') {
  if (!o) putchar('0');
  if (o < 0) o = -o, putchar('-');
  while (o) wr[++rw] = o % 10, o /= 10;
  while (rw) putchar(wr[rw--] + '0');
  putchar(c);
}
template <typename ra>
inline void cmin(ra &a, ra b) {
  if (a > b) a = b;
}
template <typename ra>
inline void cmax(ra &a, ra b) {
  if (a < b) a = b;
}
template <typename ra>
inline bool ckmin(ra &a, ra b) {
  return (a > b) ? a = b, 1 : 0;
}
template <typename ra>
inline bool ckmax(ra &a, ra b) {
  return (a < b) ? a = b, 1 : 0;
}
}  // namespace remoon
using namespace std;
using namespace remoon;
namespace mod_zone {
inline void inc(int &a, int b) {
  a += b;
  if (a >= 998244353) a -= 998244353;
}
inline void dec(int &a, int b) {
  a -= b;
  if (a < 0) a += 998244353;
}
inline int Inc(int a, int b) {
  return (a + b >= 998244353) ? a + b - 998244353 : a + b;
}
inline int Dec(int a, int b) { return (a - b < 0) ? a - b + 998244353 : a - b; }
inline int mul(int a, int b) { return 1ll * a * b % 998244353; }
inline int fp(int a, int k) {
  int ret = 1;
  for (; k; k >>= 1, a = mul(a, a))
    if (k & 1) ret = mul(ret, a);
  return ret;
}
}  // namespace mod_zone
using namespace mod_zone;
bool v[2005][2005];
char s[2005][2005];
int n, k, f[2005][2005];
int main() {
  n = read();
  k = read();
  for (register int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  for (register int i = 1; i <= n; i++)
    for (register int j = 1; j <= n; j++) {
      f[i][j] = max(f[i - 1][j], f[i][j - 1]);
      if (s[i][j] == 'a') f[i][j]++;
      if (i + j - 1 - f[i][j] <= k) s[i][j] = 'a';
    }
  putchar(s[1][1]);
  v[1][1] = 1;
  for (register int i = 3; i <= n + n; i++) {
    char nxt = 'z';
    for (register int x = 1; x <= i; x++) {
      int y = i - x;
      if (x > n || y > n) continue;
      if (!v[x - 1][y] && !v[x][y - 1]) continue;
      cmin(nxt, s[x][y]);
    }
    putchar(nxt);
    for (register int x = 1; x <= i; x++) {
      int y = i - x;
      if (x > n || y > n) continue;
      if (!v[x - 1][y] && !v[x][y - 1]) continue;
      if (s[x][y] == nxt) v[x][y] = 1;
    }
  }
  return 0;
}
