#include <bits/stdc++.h>
using namespace std;
using namespace rel_ops;
using ll = int64_t;
using Pii = pair<int, int>;
using ull = uint64_t;
using Vi = vector<int>;
void run();
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  run();
  return 0;
}
int uplg(int n) { return 32 - __builtin_clz(n); }
int uplg(ll n) { return 64 - __builtin_clzll(n); }
int cmp(double a, double b, double eps = 1e-9) {
  return (a > b + eps) - (a + eps < b);
}
char board[2001][2001];
int n, k;
int dp[2001][2001];
int lex[2001][2001];
bool toRight[2001][2001];
void run() {
  cin >> n >> k;
  for (int i = (0); i < (n); i++) cin >> board[i];
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) {
      if (i == 0 && j == 0) {
        dp[i][j] = 0;
      } else {
        dp[i][j] = INT_MAX;
      }
      if (i > 0) {
        dp[i][j] = min(dp[i][j], dp[i - 1][j]);
      }
      if (j > 0) {
        dp[i][j] = min(dp[i][j], dp[i][j - 1]);
      }
      if (board[i][j] != 'a') {
        dp[i][j]++;
      }
    }
  if (dp[n - 1][n - 1] <= k) {
    for (int i = (0); i < (n * 2 - 1); i++) cout << 'a';
    cout << endl;
    return;
  }
  lex[n][n] = 0;
  Pii from{0, 0};
  for (int sum = n * 2 - 1; sum >= 0; sum--) {
    vector<pair<Pii, int>> pairs;
    int best = INT_MAX;
    Pii bestPos = {-1, -1};
    for (int i = (0); i < (n); i++) {
      int j = sum - i;
      if (j < 0 || j >= n) continue;
      int better = INT_MAX;
      if (j + 1 < n) better = min(better, lex[i][j + 1]);
      if (i + 1 < n) {
        better = min(better, lex[i + 1][j]);
        if (better == lex[i + 1][j]) toRight[i][j] = 1;
      }
      pairs.push_back({{board[i][j], better}, i});
      if (dp[i][j] <= k) {
        if (better < best) {
          best = better;
          bestPos = {i, j};
        }
      }
    }
    if (best < INT_MAX) {
      from = bestPos;
      if (toRight[bestPos.first][bestPos.second])
        from.first++;
      else
        from.second++;
      break;
    }
    sort((pairs).begin(), (pairs).end());
    Pii last = {-1, -1};
    int ind = 0;
    for (auto& p : (pairs)) {
      if (p.first != last) {
        ind++;
        last = p.first;
      }
      lex[p.second][sum - p.second] = ind;
    }
  }
  for (int i = (0); i < (from.first + from.second); i++) cout << 'a';
  while (from.first != n - 1 || from.second != n - 1) {
    cout << board[from.first][from.second];
    if (toRight[from.first][from.second])
      from.first++;
    else
      from.second++;
  }
  cout << board[n - 1][n - 1] << endl;
}
