#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int f[N][N];
char a[N][N];
char us[N][N];
vector<pair<int, int> > g[2 * N + 28];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) cin >> a[i][j];
  if (n == 1) {
    if (a[0][0] != 'a' && k) a[0][0] = 'a';
    cout << a[0][0];
    return 0;
  }
  f[0][0] = a[0][0] != 'a';
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) {
      if (!(i + j)) continue;
      if (!i) f[i][j] = f[i][j - 1] + (a[i][j] != 'a');
      if (!j) f[i][j] = f[i - 1][j] + (a[i][j] != 'a');
      if (i && j) f[i][j] = min(f[i - 1][j], f[i][j - 1]) + (a[i][j] != 'a');
    }
  if (f[n - 1][n - 1] <= k) {
    for (int i = 0; i < 2 * n - 1; ++i) cout << 'a';
    return 0;
  }
  int mx = -1;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (f[i][j] == k) mx = max(mx, i + j);
  string ans;
  if (k == 0)
    g[0].push_back({0, 0}), ans += a[0][0];
  else
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (f[i][j] == k && mx == i + j) g[0].push_back({i, j});
  for (int i = 0; i < mx + 1; ++i) ans += 'a';
  int lv = 0;
  while (!us[n - 1][n - 1]) {
    char mn = 'z';
    for (pair<int, int> cur : g[lv]) {
      int i = cur.first, j = cur.second;
      if (i < n - 1) mn = min(mn, a[i + 1][j]);
      if (j < n - 1) mn = min(mn, a[i][j + 1]);
    }
    ans += mn;
    for (pair<int, int> cur : g[lv]) {
      int i = cur.first, j = cur.second;
      if (i < n - 1 && !us[i + 1][j] && a[i + 1][j] == mn) {
        us[i + 1][j] = 1;
        g[lv + 1].push_back({i + 1, j});
      }
      if (j < n - 1 && !us[i][j + 1] && a[i][j + 1] == mn) {
        us[i][j + 1] = 1;
        g[lv + 1].push_back({i, j + 1});
      }
    }
    ++lv;
  }
  cout << ans;
}
