#include <bits/stdc++.h>
char grid[2010][2010];
short int f[2010][2010];
std::set<std::pair<short int, short int>> sec;
short int n, k;
std::string ans;
int main(int argc, char *argv[]) {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cout.tie(0);
  std::cin >> n >> k;
  memset(f, 0x3f, sizeof(f));
  for (short int i = 1; i <= n; i++) {
    std::cin >> (grid[i] + 1);
  }
  f[0][0] = 0;
  f[0][1] = 0;
  f[1][0] = 0;
  ans = "";
  for (short int i = 1; i <= n; i++) {
    for (short int j = 1; j <= n; j++) {
      if (f[i - 1][j] > f[i][j - 1]) {
        f[i][j] = f[i][j - 1] + (grid[i][j] != 'a');
      } else {
        f[i][j] = f[i - 1][j] + (grid[i][j] != 'a');
      }
    }
  }
  short int maxp = 0;
  for (short int i = 1; i <= n; i++) {
    for (short int j = 1; j <= n; j++) {
      if (f[i][j] <= k) {
        if (i + j > maxp) {
          maxp = i + j;
          sec.clear();
          sec.insert(std::make_pair(i, j));
        } else if (i + j == maxp) {
          sec.insert(std::make_pair(i, j));
        }
      }
    }
  }
  if (k == 0) {
    sec.clear();
    sec.insert({1, 1});
    ans.append(1, grid[1][1]);
    maxp = 1;
  }
  ans.append(maxp - 1, 'a');
  short int dir[2][2] = {{1, 0}, {0, 1}};
  for (short int i = maxp; i <= 2 * n; i++) {
    std::set<std::pair<short int, short int>> tp;
    for (auto j : sec) {
      short int x = j.first;
      short int y = j.second;
      for (short int k = 0; k < 2; k++) {
        short int xx = x + dir[k][0];
        short int yy = y + dir[k][1];
        if (xx > n || yy > n) {
          continue;
        }
        tp.insert({xx, yy});
      }
    }
    char minc = 'z' + 1;
    for (auto j : tp) {
      minc = std::min(minc, grid[j.first][j.second]);
    }
    sec.clear();
    for (auto j : tp) {
      if (grid[j.first][j.second] == minc) {
        sec.insert(j);
      }
    }
    if (minc != 'z' + 1) {
      ans.append(1, minc);
    }
  }
  std::cout << ans << std::endl;
  return 0;
}
