#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int n, k, a[2005];
char mp[2005][2005];
int need[2005][2005];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i == 1 && j == 1)
        need[i][j] = 0;
      else
        need[i][j] = 1000000000;
      if (i > 1) need[i][j] = min(need[i][j], need[i - 1][j]);
      if (j > 1) need[i][j] = min(need[i][j], need[i][j - 1]);
      if (mp[i][j] != 'a') need[i][j]++;
    }
  if (need[n][n] <= k) {
    for (int i = 0; i < 2 * n - 1; i++) printf("a");
    return 0;
  }
  int cur = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (need[i][j] <= k) cur = max(cur, i + j - 1);
  string ans(cur, 'a');
  vector<pair<int, int> > v;
  for (int i = 1; i <= n; i++) {
    int j = cur + 1 - i;
    if (j < 1 || j > n) continue;
    if (need[i][j] <= k) v.push_back(pair<int, int>(i, j));
  }
  if (cur == 0) {
    cur++;
    ans += mp[1][1];
    v.push_back(pair<int, int>(1, 1));
  }
  for (int i = cur + 1; i <= 2 * n - 1; i++) {
    vector<pair<int, int> > valid;
    valid.clear();
    for (auto it : v) {
      if (it.first < n)
        valid.push_back(pair<int, int>(it.first + 1, it.second));
      if (it.second < n)
        valid.push_back(pair<int, int>(it.first, it.second + 1));
    }
    sort(valid.begin(), valid.end());
    valid.erase(unique(valid.begin(), valid.end()), valid.end());
    char now = 'z';
    for (auto it : valid) now = min(now, mp[it.first][it.second]);
    ans += now;
    v.clear();
    for (auto it : valid)
      if (mp[it.first][it.second] == now) v.push_back(it);
  }
  cout << ans << endl;
  return 0;
}
