#include <bits/stdc++.h>
using namespace std;
char ch[2010][2010];
int dp[2010][2010];
int gg[2010][2010];
char ch1[5000];
int main(void) {
  int n, k;
  scanf("%d%d", &n, &k);
  memset(dp, 0, sizeof(dp));
  memset(gg, 0, sizeof(gg));
  for (int i = 0; i < n; i++) {
    getchar();
    for (int z = 0; z < n; z++) {
      scanf("%c", &ch[i][z]);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int z = 0; z < n; z++) {
      if (i == 0)
        dp[i][z] = dp[i][max(z - 1, 0)];
      else if (z == 0)
        dp[i][z] = dp[max(i - 1, 0)][z];
      else
        dp[i][z] = min(dp[i][z - 1], dp[i - 1][z]);
      if (dp[i][z] < k) {
        if (ch[i][z] != 'a') {
          dp[i][z] += 1;
          ch[i][z] = 'a';
        }
      }
    }
  }
  int ans = 0;
  gg[0][0] = 1;
  for (int i = 0; i < 2 * n - 1; i++) {
    int tot = min(n, i + 1);
    char minn = 'z';
    for (int x = max(0, -n + i + 1); x < tot; x++) {
      int y = i - x;
      int x1 = x;
      if (x1 >= 0 && y >= 0 && x1 < n && y < n &&
          (gg[max(x1 - 1, 0)][y] || gg[x1][max(y - 1, 0)])) {
        minn = min(minn, ch[x1][y]);
      }
    }
    for (int x = max(0, -n + i + 1); x < tot; x++) {
      int y = i - x;
      int x1 = x;
      if (x1 >= 0 && y >= 0 && x1 < n && y < n &&
          (gg[max(x1 - 1, 0)][y] || gg[x1][max(y - 1, 0)]) &&
          ch[x1][y] == minn) {
        gg[x1][y] = 1;
      }
    }
    ch1[ans++] = minn;
  }
  for (int i = 0; i < ans; i++) {
    printf("%c", ch1[i]);
  }
  printf("\n");
  return 0;
}
