#include <bits/stdc++.h>
const long long MOD = 1e9 + 7;
const long long INF = 1011111111;
const long long LLINF = 1000111000111000111LL;
const long double EPS = 1e-10;
const long double PI = 3.14159265358979323;
using namespace std;
long long powm(long long base, long long exp, long long mod = MOD) {
  long long ans = 1;
  while (exp) {
    if (exp & 1) ans = (ans * base) % mod;
    exp >>= 1, base = (base * base) % mod;
  }
  return ans;
}
const long long N = 2005;
long long minm[N][N], poss[2 * N];
char a[N][N], diagmin[2 * N];
long long mk[N][N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, k;
  cin >> n >> k;
  for (long long i = 1; i < n + 1; i++)
    for (long long j = 1; j < n + 1; j++) cin >> a[i][j];
  for (long long i = 0; i < N; i++)
    for (long long j = 0; j < N; j++) minm[i][j] = LLINF;
  minm[1][1] = (a[1][1] != 'a');
  for (long long i = 1; i < n + 1; i++)
    for (long long j = 1; j < n + 1; j++) {
      if (i == 1 and j == 1) continue;
      minm[i][j] = (a[i][j] != 'a') + min(minm[i - 1][j], minm[i][j - 1]);
    }
  if (minm[n][n] <= k) {
    for (long long i = 1; i < 2 * n; i++) cout << "a";
    return 0;
  }
  for (long long i = 1; i < n + 1; i++)
    for (long long j = 1; j < n + 1; j++)
      if (minm[i][j] <= k) poss[i + j] = 1;
  for (long long i = 1; i < n + 1; i++)
    for (long long j = 1; j < n + 1; j++)
      if (minm[i][j] == k) mk[i][j] = 1;
  long long max_reach = 1;
  for (long long i = 2; i < 2 * n + 1; i++)
    if (poss[i]) max_reach = i;
  for (long long i = 2; i < max_reach + 1; i++) diagmin[i] = 'a';
  if (max_reach == 1) mk[0][1] = mk[1][0] = 1;
  for (long long diag = max_reach + 1; diag < 2 * n + 1; diag++) {
    char curr_min = 'z';
    for (long long i = 1; i < n + 1; i++) {
      long long j = diag - i;
      if (j >= 1 and j <= n) {
        if (mk[i - 1][j] or mk[i][j - 1]) {
          curr_min = min(curr_min, a[i][j]);
        }
      }
    }
    diagmin[diag] = curr_min;
    for (long long i = 1; i < n + 1; i++) {
      long long j = diag - i;
      if (j >= 1 and j <= n) {
        if ((mk[i - 1][j] or mk[i][j - 1]) and curr_min == a[i][j]) {
          mk[i][j] = 1;
        }
      }
    }
  }
  for (long long i = 2; i < 2 * n + 1; i++) cout << diagmin[i];
  return 0;
}
