#include <bits/stdc++.h>
using namespace std;
int n, k, dis[2002][2002], c[2002][2002], mx;
char a[2002][2002];
void dfs(int i, int j) {
  queue<pair<int, int>> q;
  q.push({1, 1});
  while (q.size()) {
    i = q.front().first;
    j = q.front().second;
    q.pop();
    if (c[i][j] + k >= dis[i][j] - 1 && dis[i][j] > mx) mx = dis[i][j];
    if (i == n && j == n) continue;
    int t = 0;
    if (a[i][j] == 'a') t = 1;
    if (i + 1 <= n && (dis[i + 1][j] == 0 || c[i + 1][j] < c[i][j] + t)) {
      c[i + 1][j] = c[i][j] + t;
      dis[i + 1][j] = dis[i][j] + 1;
      q.push({i + 1, j});
    }
    if (j + 1 <= n && (dis[i][j + 1] == 0 || c[i][j + 1] < c[i][j] + t)) {
      c[i][j + 1] = c[i][j] + t;
      dis[i][j + 1] = dis[i][j] + 1;
      q.push({i, j + 1});
    }
  }
}
set<pair<char, pair<int, int>>> s[2];
string ans;
void get() {
  int r = 0;
  while (1) {
    auto t = *s[r].begin();
    ans.push_back(t.first);
    if (t.second.first == n && t.second.second == n) break;
    for (auto p : s[r]) {
      if (p.first == t.first) {
        if (p.second.first + 1 <= n)
          s[!r].insert({a[p.second.first + 1][p.second.second],
                        {p.second.first + 1, p.second.second}});
        if (p.second.second + 1 <= n)
          s[!r].insert({a[p.second.first][p.second.second + 1],
                        {p.second.first, p.second.second + 1}});
      }
    }
    s[r].clear();
    r = !r;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> a[i][j];
  dis[1][1] = 1;
  dfs(1, 1);
  if (mx == n * 2 - 1 && k + mx - 1 >= n * 2 - 1) {
    for (int i = 1; i <= mx; i++) cout << "a";
    return 0;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (dis[i][j] == mx && c[i][j] + k >= dis[i][j] - 1) {
        s[0].insert({a[i][j], {i, j}});
      }
    }
  get();
  for (int i = 1; i <= mx - 1; i++) cout << "a";
  cout << ans;
  return 0;
}
