#include <bits/stdc++.h>
using namespace std;
int n, k, p[2001][2001], mn[4444], mx, was;
char a[2001][2001];
queue<pair<int, pair<int, int> > > q;
set<pair<pair<int, char>, pair<int, int> > > mq;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) cin >> a[i][j];
  for (int i = 0; i < 2 * n + 1; i++) mn[i] = 1000000000;
  q.push({-k - 1, {0, 0}});
  while (!q.empty()) {
    int x, y, c;
    x = q.front().second.first;
    y = q.front().second.second;
    c = -(q.front().first);
    q.pop();
    if (p[x][y] > c) continue;
    p[x][y] = c;
    if (c != 1) mx = max(mx, x + y + 1);
    if (a[x][y] != 'a') c--;
    if (x + 1 < n && p[x + 1][y] < c) {
      p[x + 1][y] = c;
      q.push({-c, {x + 1, y}});
    }
    if (y + 1 < n && p[x][y + 1] < c) {
      p[x][y + 1] = c;
      q.push({-c, {x, y + 1}});
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (p[i][j] == 1) mq.insert({{i + j + 1, a[i][j]}, {i, j}});
  for (int i = 1; i <= mx; i++) mn[i] = 0;
  while (!mq.empty()) {
    int sum, x, y;
    char c;
    x = mq.begin()->second.first;
    y = mq.begin()->second.second;
    c = a[x][y];
    sum = x + y + 1;
    mq.erase(mq.begin());
    if (sum < was || c - 'a' > mn[sum]) continue;
    if (sum > was) was = sum;
    mn[sum] = min(mn[sum], c - 'a');
    if (x + 1 < n && !p[x + 1][y]) {
      p[x + 1][y] = 1;
      mq.insert({{x + y + 2, a[x + 1][y]}, {x + 1, y}});
    }
    if (y + 1 < n && !p[x][y + 1]) {
      p[x][y + 1] = 1;
      mq.insert({{x + y + 2, a[x][y + 1]}, {x, y + 1}});
    }
  }
  for (int i = 1; i <= n * 2 - 1; i++) cout << (char)(mn[i] + 'a');
}
