#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e+3 + 50;
int n, m;
char g[MAXN][MAXN];
int num[MAXN][MAXN];
int vis[MAXN][MAXN];
void init() {
  memset(num, 0, sizeof(num));
  memset(vis, 0, sizeof(vis));
}
int main() {
  while (cin >> n >> m) {
    getchar();
    for (int i = 1; i <= n; i++) {
      scanf("%s", g[i] + 1);
    }
    init();
    int minA = 0;
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= n; k++) {
        if (i > 1 && k > 1) {
          num[i][k] = min(num[i - 1][k], num[i][k - 1]);
        } else if (i > 1) {
          num[i][k] = num[i - 1][k];
        } else if (k > 1) {
          num[i][k] = num[i][k - 1];
        }
        num[i][k] += (g[i][k] != 'a');
        if (num[i][k] <= m) {
          minA = max(minA, i + k - 1);
        }
      }
    }
    queue<int> p, q;
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= n; k++) {
        if (num[i][k] <= m && i + k - 1 == minA) {
          p.push(i);
          p.push(k);
        }
      }
    }
    string ans = "";
    for (int i = 1; i <= minA; i++) {
      ans += 'a';
    }
    if (minA == 0) {
      p.push(1);
      p.push(1);
      ans += g[1][1];
      minA = 1;
    }
    for (int i = minA + 1; i <= 2 * n - 1; i++) {
      q = p;
      char next = 'z';
      while (!p.empty()) {
        int x = p.front();
        p.pop();
        int y = p.front();
        p.pop();
        if (x + 1 <= n) {
          next = min(next, g[x + 1][y]);
        }
        if (y + 1 <= n) {
          next = min(next, g[x][y + 1]);
        }
      }
      ans += next;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        int y = q.front();
        q.pop();
        if (x + 1 <= n && g[x + 1][y] == next && !vis[x + 1][y]) {
          p.push(x + 1);
          p.push(y);
          vis[x + 1][y] = 1;
        }
        if (y + 1 <= n && g[x][y + 1] == next && !vis[x][y + 1]) {
          p.push(x);
          p.push(y + 1);
          vis[x][y + 1] = 1;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}
