#include <bits/stdc++.h>
using namespace std;
struct re {
  int x, y;
};
int n, K, f[2001][2001];
char mp[2001][2001];
vector<re> A, B, zy[4001];
string Ans;
void upd(int &x, int y) {
  if (y <= K) {
    if (x == -1) x = y;
    if (y < x) x = y;
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      f[i][j] = -1;
      zy[i + j - 1].push_back((re){i, j});
    }
  if (mp[1][1] == 'a') {
    Ans.push_back('a');
    A.push_back((re){1, 1});
    f[1][1] = 0;
  } else {
    if (K >= 1) {
      Ans.push_back('a');
      A.push_back((re){1, 1});
      f[1][1] = 1;
    } else {
      Ans.push_back(mp[1][1]);
      A.push_back((re){1, 1});
      f[1][1] = 0;
    }
  }
  for (int i = 2; i <= 2 * n - 1; ++i) {
    char Min = 'z';
    for (auto u : A) {
      if (f[u.x][u.y] + 1 <= K) Min = 'a';
      if (u.x + 1 <= n) Min = min(Min, mp[u.x + 1][u.y]);
      if (u.y + 1 <= n) Min = min(Min, mp[u.x][u.y + 1]);
    }
    Ans.push_back(Min);
    for (auto u : A) {
      if (u.x + 1 <= n) {
        upd(f[u.x + 1][u.y], f[u.x][u.y] + (mp[u.x + 1][u.y] != Min));
      }
      if (u.y + 1 <= n) {
        upd(f[u.x][u.y + 1], f[u.x][u.y] + (mp[u.x][u.y + 1] != Min));
      }
    }
    for (auto u : zy[i])
      if (f[u.x][u.y] != -1) B.push_back(u);
    swap(A, B);
    B.clear();
  }
  printf("%s\n", Ans.c_str());
  return 0;
}
