#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000000 + 7;
int addm(int& a, int b) { return (a += b) < mod ? a : a -= mod; }
template <class T, class U>
bool smin(T& a, U b) {
  return a > b ? (a = b, 1) : 0;
}
template <class T, class U>
bool smax(T& a, U b) {
  return a < b ? (a = b, 1) : 0;
}
int dp[2000][2000];
string bd[2000];
int k;
int n, m;
vector<pair<int, int> > bests[2];
int io[]{1, 0};
int jo[]{0, 1};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  m = n;
  for (int i = 0; i < n; ++i) cin >> bd[i];
  fill(dp[0], dp[n], INT_MAX / 2);
  dp[0][0] = (bd[0][0] != 'a');
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (i) smin(dp[i][j], dp[i - 1][j] + (bd[i][j] != 'a'));
      if (j) smin(dp[i][j], dp[i][j - 1] + (bd[i][j] != 'a'));
    }
  int p = 0;
  int Ma = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (dp[i][j] <= k) smax(Ma, i + j + 1);
    }
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (dp[i][j] <= k && i + j + 1 == Ma) bests[0].emplace_back(i, j);
    }
  int len;
  string result;
  if (Ma == 0) {
    bests[0].emplace_back(0, 0);
    len = 1;
    result.push_back(bd[0][0]);
  } else {
    len = Ma;
    result = string(Ma, 'a');
  }
  while (len < n + m - 1) {
    char mchar = 'z';
    for (int l = 0; l < bests[p].size(); ++l)
      for (int c = 0; c < 2; ++c) {
        int i = bests[p][l].first;
        int j = bests[p][l].second;
        int ni = i + io[c];
        int nj = j + jo[c];
        if (ni < n && nj < m) smin(mchar, bd[ni][nj]);
      }
    for (int l = 0; l < bests[p].size(); ++l)
      for (int c = 0; c < 2; ++c) {
        int i = bests[p][l].first;
        int j = bests[p][l].second;
        int ni = i + io[c];
        int nj = j + jo[c];
        if (ni < n && nj < m && bd[ni][nj] == mchar)
          bests[1 - p].emplace_back(ni, nj);
      }
    p = 1 - p;
    sort(bests[p].begin(), bests[p].end());
    bests[p].resize(unique(bests[p].begin(), bests[p].end()) -
                    bests[p].begin());
    result.push_back(mchar);
    bests[1 - p].clear();
    ++len;
  }
  cout << result << endl;
}
