#include <bits/stdc++.h>
using namespace std;
inline void file() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
int n, k;
char s[2001][2001];
int dp[2001][2001];
bool was[2001][2001];
string ans = "";
vector<pair<int, int> > cur[5001];
int maxdp = 0;
inline void build() {
  for (int i = 0; i <= n; i++) dp[0][i] = dp[i][0] = 1e9;
  dp[0][1] = dp[1][0] = 0;
  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]) + (s[i][j] != 'a');
      if (dp[i][j] == k) maxdp = max(maxdp, i + j);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dp[i][j] == k && i + j == maxdp) {
        cur[0].push_back({i, j});
        was[i][j] = true;
      }
    }
  }
}
int main() {
  file();
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) cin >> s[i][j];
  }
  build();
  if (dp[n][n] <= k) {
    for (int i = 0; i < 2 * n - 1; i++) cout << 'a';
    return 0;
  }
  if (!k) {
    cur[0].push_back({1, 1});
    ans += s[1][1];
  }
  for (int t = 0; cur[t].size(); t++) {
    assert(t <= 2 * n - 1);
    char sn = 'z';
    for (int i = 0; i < cur[t].size(); i++) {
      int x = cur[t][i].first, y = cur[t][i].second;
      if (x < n) sn = min(sn, s[x + 1][y]);
      if (y < n) sn = min(sn, s[x][y + 1]);
    }
    ans += sn;
    for (int i = 0; i < cur[t].size(); i++) {
      int x = cur[t][i].first, y = cur[t][i].second;
      if (x < n && s[x + 1][y] == sn && !was[x + 1][y]) {
        was[x + 1][y] = true;
        cur[t + 1].push_back({x + 1, y});
      }
      if (y < n && s[x][1 + y] == sn && !was[x][y + 1]) {
        was[x][y + 1] = true;
        cur[t + 1].push_back({x, y + 1});
      }
    }
  }
  for (int i = 0; i < min(2 * n - 1, maxdp - 1); i++) cout << "a";
  if (ans.size()) {
    cout << ans.substr(0, ans.size() - 1);
  }
  return 0;
}
