#include <bits/stdc++.h>
using namespace std;
const int MAX = 2005, mf[2] = {1, 0}, mc[2] = {0, 1}, INF = 1e9;
int n, k, dp[MAX][MAX], opt[MAX][MAX];
pair<int, int> from[MAX][MAX];
vector<pair<int, int> > ans;
char a[MAX][MAX];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
  dp[1][1] = (a[1][1] != 'a');
  if (dp[1][1] > k) dp[1][1] = INF;
  for (int i = 2; i <= n; i++) {
    dp[1][i] = dp[1][i - 1] + (a[1][i] != 'a');
    dp[i][1] = dp[i - 1][1] + (a[i][1] != 'a');
    if (dp[1][i] > k) dp[1][i] = INF;
    if (dp[i][1] > k) dp[i][1] = INF;
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 2; j <= n; j++) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (a[i][j] != 'a');
      if (dp[i][j] > k) dp[i][j] = INF;
    }
  }
  vector<pair<int, int> > q;
  q.push_back({1, 1});
  while (!q.empty()) {
    set<pair<int, int> > s;
    char best = 'z';
    best++;
    for (auto o : q) {
      int f = o.first;
      int c = o.second;
      opt[f][c] = 1;
      for (int i = 0; i < 2; i++) {
        int nf = f + mf[i];
        int nc = c + mc[i];
        if (nf < 1 || nf > n || nc < 1 || nc > n) continue;
        if (a[nf][nc] < best) best = a[nf][nc];
        if (dp[nf][nc] <= k) best = 'a';
      }
    }
    for (auto o : q) {
      int f = o.first;
      int c = o.second;
      for (int i = 0; i < 2; i++) {
        int nf = f + mf[i];
        int nc = c + mc[i];
        if (nf < 1 || nf > n || nc < 1 || nc > n) continue;
        if (a[nf][nc] == best || dp[nf][nc] <= k) {
          from[nf][nc] = {f, c};
          s.insert({nf, nc});
        }
      }
    }
    for (auto o : s) {
      int f = o.first, c = o.second;
      if (dp[f][c] <= k) {
        if (opt[f - 1][c] && dp[f - 1][c] + (a[f][c] != 'a') == dp[f][c]) {
          from[f][c] = {f - 1, c};
        } else if (opt[f][c - 1] &&
                   dp[f][c - 1] + (a[f][c] != 'a') == dp[f][c]) {
          from[f][c] = {f, c - 1};
        }
      }
    }
    for (auto o : q) opt[o.first][o.second] = 0;
    q.clear();
    for (auto o : s) q.push_back(o);
  }
  int f = n, c = n;
  while (1) {
    int nf = from[f][c].first;
    int nc = from[f][c].second;
    ans.push_back({f, c});
    if (nf == 0 && nc == 0) break;
    f = nf, c = nc;
  }
  reverse(ans.begin(), ans.end());
  string res = "";
  for (auto o : ans) res.push_back(a[o.first][o.second]);
  for (int i = 0; i < (int)res.size(); i++) {
    if (res[i] != 'a') {
      k--;
      if (k < 0) break;
      res[i] = 'a';
    }
  }
  printf("%s\n", res.c_str());
  return 0;
}
