#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
char a[2010][2010];
int cz[2010][2010];
set<pair<int, int> > cur, nex;
char getmin(int n) {
  char tmp = 'z';
  nex.clear();
  for (auto p : cur) {
    int x = p.first, y = p.second;
    if (x < n) tmp = min(tmp, a[x + 1][y]);
    if (y < n) tmp = min(tmp, a[x][y + 1]);
  }
  for (auto p : cur) {
    int x = p.first, y = p.second;
    if (x < n && a[x + 1][y] == tmp) nex.insert({x + 1, y});
    if (y < n && a[x][y + 1] == tmp) nex.insert({x, y + 1});
  }
  cur = nex;
  return tmp;
}
int main() {
  memset(cz, 0x3f, sizeof(cz));
  int n, K, Lb = 0;
  cin >> n >> K;
  for (int i = (1); i <= (n); i++) scanf("%s", a[i] + 1);
  cz[1][1] = 0;
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (n); j++) {
      if (i > 1 && cz[i - 1][j] != -1) cz[i][j] = min(cz[i][j], cz[i - 1][j]);
      if (j > 1 && cz[i][j - 1] != -1) cz[i][j] = min(cz[i][j], cz[i][j - 1]);
      if (a[i][j] != 'a') cz[i][j]++;
      if (cz[i][j] <= K) Lb = max(Lb, i + j);
    }
  Lb = max(Lb - 1, 0);
  if (Lb == 0) {
    putchar(a[1][1]);
    cur.insert({1, 1});
    Lb++;
  } else {
    for (int i = (1); i <= (Lb); i++) putchar('a');
    for (int i = (max(Lb - n + 1, 1)); i <= (n); i++)
      if (cz[i][Lb - i + 1] <= K) cur.insert({i, Lb - i + 1});
  }
  for (int i = (Lb + 1); i <= (2 * n - 1); i++) putchar(getmin(n));
}
