#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
char a[N][N];
int dp[N][N];
char ans[N * 2];
bool vis[N][N];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
  for (int i = 2; i <= n; i++) dp[i][0] = dp[0][i] = N;
  int mx = -1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (a[i][j] != 'a');
      if (dp[i][j] <= m && i + j > mx) {
        mx = i + j;
      }
    }
  vector<pair<int, int> > can;
  if (mx == -1) {
    can.push_back(make_pair(1, 1));
    ans[0] = a[1][1];
    mx = 2;
  } else {
    for (int i = 0; i <= mx - 2; i++) ans[i] = 'a';
    for (int i = 1; i <= n; i++) {
      int j = mx - i;
      if (j <= 0 || j > n) continue;
      if (dp[i][j] <= m) can.push_back(make_pair(i, j));
    }
  }
  for (int i = mx + 1; i <= 2 * n; i++) {
    vector<pair<int, int> > p;
    char mn = 'z' + 1;
    for (auto j : can) {
      int x = j.first, y = j.second;
      if (x + 1 <= n) mn = min(mn, a[x + 1][y]);
      if (y + 1 <= n) mn = min(mn, a[x][y + 1]);
    }
    for (auto j : can) {
      int x = j.first, y = j.second;
      if (a[x + 1][y] == mn && !vis[x + 1][y]) {
        vis[x + 1][y] = 1;
        p.push_back(make_pair(x + 1, y));
      }
      if (a[x][y + 1] == mn && !vis[x][y + 1]) {
        vis[x][y + 1] = 1;
        p.push_back(make_pair(x, y + 1));
      }
    }
    ans[i - 2] = mn;
    swap(can, p);
  }
  printf("%s\n", ans);
  return 0;
}
