#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long kk = 0, f = 1;
  char cc = getchar();
  while (cc < '0' || cc > '9') {
    if (cc == '-') f = -1;
    cc = getchar();
  }
  while (cc >= '0' && cc <= '9') {
    kk = (kk << 1) + (kk << 3) + cc - '0';
    cc = getchar();
  }
  return kk * f;
}
const int maxn = 2022;
char cun[2 * maxn + 11], out[2 * maxn + 11], op[maxn + 10][maxn + 10];
int n, k, ma;
bool vis[maxn + 11][maxn + 11];
int dp[maxn + 11][maxn + 11];
struct zj {
  int x, y;
};
queue<zj> Q;
void bfs() {
  zj now;
  queue<zj> q;
  while (!Q.empty()) {
    now = Q.front();
    Q.pop();
    q.push(now);
  }
  for (int i = 0; i < ma; ++i) cun[i] = 'a';
  if (ma == 0) {
    q.push((zj){1, 1});
    cun[0] = op[1][1];
    ma++;
  }
  for (int i = ma; i < 2 * n - 1; ++i) {
    char cc = 'z';
    while (!q.empty()) {
      now = q.front();
      Q.push(now);
      q.pop();
      if (now.x + 1 <= n) cc = min(cc, op[now.x + 1][now.y]);
      if (now.y + 1 <= n) cc = min(cc, op[now.x][now.y + 1]);
    }
    cun[i] = cc;
    while (!Q.empty()) {
      now = Q.front();
      Q.pop();
      if (now.x + 1 <= n && op[now.x + 1][now.y] == cc &&
          !vis[now.x + 1][now.y]) {
        q.push((zj){now.x + 1, now.y});
        vis[now.x + 1][now.y] = 1;
      }
      if (now.y + 1 <= n && op[now.x][now.y + 1] == cc &&
          !vis[now.x][now.y + 1]) {
        q.push((zj){now.x, now.y + 1});
        vis[now.x][now.y + 1] = 1;
      }
    }
  }
}
int main() {
  n = read();
  k = read();
  char cc;
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i <= 2 * n + 10; ++i) cun[i] = out[i] = 'z';
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      cc = getchar();
      while (cc == ' ' || cc == '\n') cc = getchar();
      op[i][j] = cc;
    }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (i > 1 && j > 1)
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
      else if (i > 1)
        dp[i][j] = dp[i - 1][j];
      else if (j > 1)
        dp[i][j] = dp[i][j - 1];
      dp[i][j] += (op[i][j] != 'a');
      if (dp[i][j] <= k) {
        ma = max(ma, i + j - 1);
      }
    }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (dp[i][j] <= k && ma == i + j - 1) {
        Q.push((zj){i, j});
      }
    }
  bfs();
  cun[2 * n - 1] = '\0';
  cout << cun;
}
