#include <bits/stdc++.h>
using namespace std;
double log(double x, double base) { return log(x) / log(base); }
int n, k;
const int maxN = 2007, INF = 1e9 + 7;
char arr[maxN][maxN];
int dp[maxN][maxN];
int hx[] = {0, 1};
int hy[] = {1, 0};
int mx, lv[maxN][maxN];
string kq = "";
bool check(int x, int y) { return (x >= 1 && y >= 1 && x <= n && y <= n); }
void bfs(queue<pair<int, int> > t) {
  queue<pair<int, int> > q, tmp;
  int curr_lv = 0;
  while (t.size()) {
    int f = t.front().first, s = t.front().second;
    q.push(t.front());
    t.pop();
  }
  if (k == 0) {
    kq += arr[1][1];
    lv[1][1] = 0;
    q.push(pair<int, int>(1, 1));
  }
  char curr_char = 'z';
  while (q.size()) {
    int u = q.front().first;
    int v = q.front().second;
    q.pop();
    int curr = lv[u][v];
    if (curr > curr_lv) {
      kq += curr_char;
      curr_char = 'z';
      curr_lv = curr;
    }
    if (u == n && v == n) return;
    for (int i = 0; i < 2; i++) {
      int dx = u + hx[i];
      int dy = v + hy[i];
      if (check(dx, dy) && lv[dx][dy] == 0) {
        if (arr[dx][dy] > curr_char) continue;
        if (arr[dx][dy] < curr_char) {
          curr_char = arr[dx][dy];
          while (tmp.size()) tmp.pop();
        }
        lv[dx][dy] = lv[u][v] + 1;
        tmp.push(pair<int, int>(dx, dy));
      }
    }
    if (q.size() == 0) {
      while (tmp.size()) {
        q.push(tmp.front());
        tmp.pop();
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      if (check(i, j)) cin >> arr[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    dp[i][0] = INF;
    dp[0][i] = INF;
  }
  dp[0][1] = 0, dp[1][0] = 0;
  queue<pair<int, int> > qu;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (arr[i][j] != 'a');
      if (dp[i][j] <= k) mx = max(i + j - 1, mx);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i + j - 1 == mx && dp[i][j] <= k) qu.push(pair<int, int>(i, j));
    }
  }
  bfs(qu);
  if (k == 0) mx--;
  for (int i = 1; i <= mx; i++) cout << 'a';
  cout << kq;
}
