#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int maxn = 2e3 + 10;
struct P {
  int r, c;
  char ch;
  P(int r = 0, int c = 0, char ch = 'z') : r(r), c(c), ch(ch) {}
};
char s[maxn][maxn];
int d[maxn][maxn], n, k, vis[maxn][maxn];
queue<P> q;
string ans = "";
void solve() {
  for (int i = 0; i < 2 * n - 1; i++) ans += 'z';
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) d[i][j] = k;
  d[0][0] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (d[i][j] == k) {
        continue;
      }
      if (i + 1 < n) d[i + 1][j] = min(d[i + 1][j], d[i][j] + (s[i][j] != 'a'));
      if (j + 1 < n) d[i][j + 1] = min(d[i][j + 1], d[i][j] + (s[i][j] != 'a'));
    }
  q.push(P(0, 0));
  while (q.size()) {
    P now = q.front();
    q.pop();
    int r = now.r, c = now.c;
    char ch = now.ch;
    if (vis[r][c]) continue;
    if (r + c > 0 && ch > ans[r + c - 1]) continue;
    vis[r][c] = 1;
    ch = s[r][c];
    if (d[r][c] < k) ch = 'a';
    ans[r + c] = min(ans[r + c], ch);
    if (r + 1 < n) q.push(P(r + 1, c, ch));
    if (c + 1 < n) q.push(P(r, c + 1, ch));
  }
  cout << ans << endl;
}
int main() {
  scanf("%d", &n);
  scanf("%d", &k);
  for (int i = 0; i < n; i++) scanf("%s", s[i]);
  solve();
  return 0;
}
