#include <bits/stdc++.h>
using namespace std;
const long long NAX = 2005;
const long long INF = 1e9 + 5;
long long dp[NAX][NAX];
char grid[NAX][NAX];
void mini(long long& a, long long b) { a = min(a, b); }
void maxi(long long& a, long long b) { a = max(a, b); }
signed main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  clock_t startT, endT;
  long long n, k;
  cin >> n >> k;
  for (long long row = 0; row < n; row++) cin >> grid[row];
  auto inside = [&](long long row, long long col) {
    return 0 <= row && 0 <= col && row < n && col < n;
  };
  startT = clock();
  for (long long i = 0; i < n; ++i)
    for (long long j = 0; j < n; ++j) dp[i][j] = INF;
  dp[0][0] = 0;
  for (long long i = 0; i < n; ++i)
    for (long long j = 0; j < n; ++j) {
      if (i != 0)
        if (i != 0) mini(dp[i][j], dp[i - 1][j]);
      if (j != 0) mini(dp[i][j], dp[i][j - 1]);
      if (grid[i][j] != 'a') ++dp[i][j];
    }
  long long pref = 0;
  for (long long i = 0; i < n; ++i)
    for (long long j = 0; j < n; ++j) {
      if (dp[i][j] <= k) maxi(pref, i + j + 1);
    }
  string ans(pref, 'a');
  vector<pair<long long, long long>> list;
  for (long long i = 0; i < n; ++i)
    for (long long j = 0; j < n; ++j) {
      if (dp[i][j] <= k && i + j + 1 == pref) list.push_back(make_pair(i, j));
    }
  if (list.empty()) {
    list.emplace_back(0, 0);
    ans += grid[0][0];
  }
  while (!list.empty()) {
    char best_char = 'z';
    vector<pair<long long, long long>> newList;
    for (auto it : list) {
      for (long long d_row : {0, 1}) {
        long long d_col = 1 - d_row;
        long long r2 = it.first + d_row;
        long long c2 = it.second + d_col;
        if (inside(r2, c2)) {
          if (grid[r2][c2] <= best_char) {
            if (grid[r2][c2] < best_char) newList.clear();
            best_char = grid[r2][c2];
            newList.push_back(make_pair(r2, c2));
          }
        }
      }
    }
    if (newList.empty()) break;
    ans += best_char;
    list = newList;
    sort(list.begin(), list.end());
    list.resize(unique(list.begin(), list.end()) - list.begin());
  }
  cout << ans << endl;
  endT = clock();
  return 0;
}
