#include <bits/stdc++.h>
using namespace std;
int n, K, deg[2020][2020], f[2020][2020], vis[2020][2020];
queue<pair<int, int> > q;
vector<pair<int, int> > V;
char s[2020][2020];
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
int main(void) {
  scanf("%d%d", &n, &K);
  for (int i = 0; i < n; i++) scanf("%s", s[i]);
  memset(f, 0x3f, sizeof f);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) deg[i][j] = bool(i) + bool(j);
  q.push({0, 0});
  f[0][0] = (s[0][0] != 'a');
  while (!q.empty()) {
    int x, y;
    tie(x, y) = q.front();
    q.pop();
    for (int i = 0; i < 2; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if (nx < 0 || ny < 0 || nx == n || ny == n) continue;
      f[nx][ny] = min(f[nx][ny], f[x][y] + (s[nx][ny] != 'a'));
      if (!--deg[nx][ny]) q.push({nx, ny});
    }
  }
  int mx = -1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (f[i][j] == K) {
        if (i + j > mx) {
          mx = i + j;
          V.clear();
          V.push_back({i, j});
        } else if (i + j == mx)
          V.push_back({i, j});
      }
  if (!~mx && K || f[n - 1][n - 1] <= K) {
    for (int i = 0; i < 2 * n - 1; i++) putchar('a');
    return 0;
  }
  for (int i = 0; i <= mx; i++) putchar('a');
  if (!K && !V.size()) {
    mx = 0;
    V.push_back({0, 0});
    putchar(s[0][0]);
  }
  while (1) {
    vector<pair<int, int> > tmp;
    tmp.clear();
    for (int i = 0; i < V.size(); i++) {
      int x, y;
      tie(x, y) = V[i];
      for (int j = 0; j < 2; j++) {
        int nx = x + dx[j], ny = y + dy[j];
        if (nx < 0 || ny < 0 || nx == n || ny == n) continue;
        if (!vis[nx][ny]) tmp.push_back({nx, ny}), vis[nx][ny] = 1;
      }
    }
    if (mx >= 2 * n - 2) break;
    ++mx;
    char bas = 'z';
    for (pair<int, int> i : tmp) bas = min(bas, s[i.first][i.second]);
    putchar(bas);
    V.clear();
    for (pair<int, int> i : tmp)
      if (s[i.first][i.second] == bas) V.push_back(i);
  }
  return 0;
}
