#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000 + 5;
char mat[MAX][MAX];
int memo[MAX][MAX];
int n, k;
int roll(int x, int y) {
  if (x == 0 || y == 0) {
    return 0;
  }
  int &ans = memo[x][y];
  if (~ans) {
    return ans;
  }
  ans = max(roll(x - 1, y), roll(x, y - 1)) + (mat[x][y] == 'a');
  return ans;
}
int main() {
  scanf("%d %d%*c", &n, &k);
  for (int i = int(1); i < int(n + 1); i++) {
    for (int j = int(1); j < int(n + 1); j++) {
      scanf("%c", &mat[i][j]);
    }
    scanf("%*c");
  }
  memset(memo, -1, sizeof memo);
  int best_dis = 0;
  vector<pair<int, int> > idxs;
  for (int i = int(1); i < int(n + 1); i++) {
    for (int j = int(1); j < int(n + 1); j++) {
      int d = (i - 1) + (j - 1) + 1;
      if (roll(i, j) + k >= d) {
        if (d > best_dis) {
          idxs.clear();
          idxs.emplace_back(i, j);
          best_dis = d;
        } else if (d == best_dis) {
          idxs.emplace_back(i, j);
        }
      }
    }
  }
  if (best_dis == 0) {
    idxs.emplace_back(1, 1);
  }
  string pref = best_dis == 0 ? string(1, mat[1][1]) : string(best_dis, 'a');
  string suf = "";
  while (idxs[0].first != n || idxs[0].second != n) {
    char best = '|';
    vector<pair<int, int> > new_idxs;
    for (auto &each : idxs) {
      for (pair<int, int> p : {pair<int, int>(0, 1), pair<int, int>(1, 0)}) {
        int nx = each.first + p.first;
        int ny = each.second + p.second;
        if (1 <= nx && nx <= n && 1 <= ny && ny <= n) {
          if (best > mat[nx][ny]) {
            new_idxs.clear();
            best = mat[nx][ny];
            new_idxs.emplace_back(nx, ny);
          } else if (best == mat[nx][ny]) {
            new_idxs.emplace_back(nx, ny);
          }
        }
      }
    }
    suf += best;
    sort(new_idxs.begin(), new_idxs.end());
    new_idxs.erase(unique(new_idxs.begin(), new_idxs.end()), new_idxs.end());
    idxs = new_idxs;
  }
  cout << pref + suf << '\n';
  return 0;
}
