#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
const int MOD = 998244353;
char C[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dp[MAXN][MAXN];
pair<int, int> link[MAXN][MAXN];
queue<pair<int, int> > Q;
int n, k;
void bfs() {
  if (Q.empty()) {
    Q.emplace(0, 0);
    vis[0][0] = true;
  }
  while (!Q.empty()) {
    vector<pair<int, int> > front;
    while (!Q.empty()) {
      front.push_back(Q.front());
      Q.pop();
    }
    sort(front.begin(), front.end(), [&](pair<int, int> x, pair<int, int> y) {
      return C[x.first][x.second] < C[y.first][y.second];
    });
    char want = C[front.front().first][front.front().second];
    for (const auto& p : front) {
      if (C[p.first][p.second] != want) continue;
      int dx[2] = {0, 1};
      int dy[2] = {1, 0};
      for (int i = 0; i < 2; i++) {
        int nr = p.first + dx[i];
        int nc = p.second + dy[i];
        if (nr < n && nc < n && !vis[nr][nc]) {
          vis[nr][nc] = true;
          link[nr][nc] = p;
          Q.emplace(nr, nc);
        }
      }
    }
  }
}
void DP() {
  memset(dp, 0x3F, sizeof(dp));
  dp[0][0] = (C[0][0] != 'a');
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (int)(C[i + 1][j] != 'a'));
      dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (int)(C[i][j + 1] != 'a'));
    }
  }
  int best = (int)(1e9);
  int blen = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dp[i][j] <= k) {
        if (i + 1 < n) blen = max(blen, i + j + 2);
        if (j + 1 < n) blen = max(blen, i + j + 2);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i + j + 2 == blen && dp[i][j] <= k) {
        if (i + 1 < n) {
          Q.emplace(i + 1, j);
          vis[i + 1][j] = true;
        }
        if (j + 1 < n) {
          Q.emplace(i, j + 1);
          vis[i][j + 1] = true;
        }
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> C[i][j];
    }
  }
  DP();
  if (dp[n - 1][n - 1] <= k) {
    cout << string(2 * n - 1, 'a') << '\n';
    exit(0);
  }
  memset(link, -1, sizeof(link));
  bfs();
  int cr = n - 1;
  int cc = n - 1;
  string res;
  while (cr != -1) {
    res += C[cr][cc];
    tie(cr, cc) = link[cr][cc];
  }
  res += string(2 * n - 1 - res.size(), 'a');
  reverse(res.begin(), res.end());
  cout << res << '\n';
  return 0;
}
