#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0;
  char ch = getchar();
  bool f = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = 1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 3) + (x << 1) + (ch ^ 48);
  return f ? -x : x;
}
const int N = 2005;
int n, k, f[N][N];
char s[N][N];
struct P {
  int x, y;
  friend inline bool operator<(const P &A, const P &B) {
    if (A.x != B.x) return A.x < B.x;
    return A.y < B.y;
  }
  friend inline bool operator==(const P &A, const P &B) {
    return A.x == B.x && A.y == B.y;
  }
};
vector<P> p, q;
inline int find() {
  int mi = 27;
  for (auto u : q) {
    if (u.x < n) mi = min(mi, s[u.x + 1][u.y] - 'a');
    if (u.y < n) mi = min(mi, s[u.x][u.y + 1] - 'a');
  }
  return mi;
}
inline void getnext(int mi) {
  for (auto u : q) {
    if (u.x < n && s[u.x + 1][u.y] - 'a' == mi) p.push_back((P){u.x + 1, u.y});
    if (u.y < n && s[u.x][u.y + 1] - 'a' == mi) p.push_back((P){u.x, u.y + 1});
  }
  sort((p).begin(), (p).end());
  p.resize(unique((p).begin(), (p).end()) - p.begin());
  q = p;
  p.clear();
}
int main() {
  n = read();
  k = read();
  if (k >= 2 * n - 1) {
    for (int i = (1), end_i = (2 * n - 1); i <= end_i; i++) putchar('a');
    return 0;
  }
  for (int i = (1), end_i = (n); i <= end_i; i++) scanf("%s", s[i] + 1);
  memset(f, 0x3f, sizeof(f));
  f[1][1] = (s[1][1] != 'a');
  int c;
  for (int i = (1), end_i = (n); i <= end_i; i++)
    for (int j = (1), end_i = (n); j <= end_i; j++) {
      c = (s[i][j] != 'a');
      if (i - 1) f[i][j] = min(f[i][j], f[i - 1][j] + c);
      if (j - 1) f[i][j] = min(f[i][j], f[i][j - 1] + c);
    }
  int mx = 0;
  for (int i = (1), end_i = (n); i <= end_i; i++)
    for (int j = (1), end_i = (n); j <= end_i; j++)
      if (f[i][j] <= k) mx = max(mx, i + j - 1);
  for (int i = (1), end_i = (mx); i <= end_i; i++) putchar('a');
  for (int i = (1), end_i = (n); i <= end_i; i++)
    for (int j = (1), end_i = (n); j <= end_i; j++)
      if (f[i][j] <= k && i + j - 1 == mx) q.push_back((P){i, j});
  if (f[1][1] == 1 && k == 0)
    k = 1, putchar(s[1][1]), q.push_back((P){1, 1}), mx = 1;
  int x;
  for (int t = (mx + 1), end_i = (2 * n - 1); t <= end_i; t++) {
    x = find();
    putchar(x + 'a');
    getnext(x);
  }
  return 0;
}
