#include <bits/stdc++.h>
using vi = std::vector<long long int>;
using vvi = std::vector<vi>;
using pii = std::pair<long long int, long long int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
using namespace std;
const long long int N = 2e3 + 10;
const long long int inf = 1e18 + 10;
long long int n, dp[N][N], k, la;
char a[N][N];
vpii s;
string second;
void solve() {
  cin >> n >> k;
  for (long long int i = 1; i <= n; i++)
    for (long long int j = 1; j <= n; j++) cin >> a[i][j];
  for (long long int i = 1; i <= n; i++)
    for (long long int j = 1; j <= n; j++)
      dp[i][j] = min(!(j != 1 and i == 1) ? dp[i - 1][j] : inf,
                     !(i != 1 and j == 1) ? dp[i][j - 1] : inf) +
                 (a[i][j] != 'a');
  for (long long int di = 1; di <= 2 * n - 1; di++) {
    long long int cost = inf;
    vpii tmp;
    for (long long int i = 1; i <= n; i++) {
      long long int j = di - i + 1;
      if (j < 1 or j > n) continue;
      if (dp[i][j] <= k) tmp.emplace_back(pii{i, j});
    }
    if (tmp.empty() == 0) s = tmp, la = di, second += 'a';
  }
  if (la != 0) {
    second = string(la, 'a');
  }
  if (la == 0) {
    if (k != 0)
      second = 'a';
    else
      second = a[1][1];
    la = 1;
    s.emplace_back(pii{1, 1});
  }
  for (long long int di = la + 1; di <= 2 * n - 1; di++) {
    vpii tm;
    char mi = 'z' + 1;
    for (auto [i, j] : s) {
      char rig = 'z' + 1, dow = 'z' + 1;
      if (i + 1 != n + 1) dow = a[i + 1][j];
      if (j + 1 != n + 1) rig = a[i][j + 1];
      if (dp[i][j] >= k) {
        mi = min({mi, dow, rig});
      }
    }
    second += (char)mi;
    for (auto [i, j] : s) {
      char rig = 'z' + 1, dow = 'z' + 1;
      if (i + 1 != n + 1) dow = a[i + 1][j];
      if (j + 1 != n + 1) rig = a[i][j + 1];
      if (dp[i][j] >= k) {
        if (dow == mi)
          tm.emplace_back(pii{i + 1, j}), a[i + 1][j] = (char)'z' + 1;
        if (rig == mi)
          tm.emplace_back(pii{i, j + 1}), a[i][j + 1] = (char)'z' + 1;
      }
    }
    s = tm;
  }
  cout << second;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
  long long int xx = 0;
  long long int t;
  cin >> t;
  while (t--) {
    ;
    solve();
    cout << "\n";
  }
  return 0;
}
