#include <bits/stdc++.h>
const int maxn = 2005;
char matrix[maxn][maxn];
char mini_path[maxn * 2];
int dp[maxn][maxn];
int dir[2][2] = {0, 1, 1, 0};
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) scanf(" %c", &matrix[i][j]);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) dp[i][j] = -3 * n;
  dp[0][0] = k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      if (dp[i][j] < 0 || matrix[i][j] != 'a') dp[i][j]--;
      for (int h = 0; h < 2; h++) {
        int di = i + dir[h][0];
        int dj = j + dir[h][1];
        if (di < n && dj < n && dp[di][dj] < dp[i][j]) dp[di][dj] = dp[i][j];
      }
    }
  if (dp[n - 1][n - 1] < 0)
    for (int i = 0; i < 2 * n - 1 + dp[n - 1][n - 1]; i++) mini_path[i] = 'a';
  else
    for (int i = 0; i < 2 * n - 1; i++) mini_path[i] = 'a';
  for (int i = 2 * n - 1 + dp[n - 1][n - 1]; i < 2 * n - 1; i++) {
    char min_char = 'z' + 1;
    for (int x = 0; x < n; x++) {
      int y = i - x;
      if (0 <= y && y < n && dp[x][y] == -1 && matrix[x][y] < min_char)
        min_char = matrix[x][y];
    }
    for (int x = 0; x < n; x++) {
      int y = i - x;
      if (0 <= y && y < n && dp[x][y] == -1 && matrix[x][y] == min_char)
        for (int h = 0; h < 2; h++) {
          int dx = x + dir[h][0];
          int dy = y + dir[h][1];
          dp[dx][dy] = -1;
        }
    }
    mini_path[i] = min_char;
  }
  mini_path[2 * n - 1] = '\0';
  printf("%s", mini_path);
  return 0;
}
