#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
int dir[2][2] = {0, 1, 1, 0}, dirnum = 2;
int n, k;
char letter_matrix[maxn][maxn];
bool flag[maxn][maxn];
int dp[maxn][maxn];
char minimum_path[2 * maxn];
void solve() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) scanf(" %c", &letter_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 || letter_matrix[i][j] != 'a') dp[i][j]--;
      for (int k = 0; k < dirnum; k++) {
        int ti = i + dir[k][0], tj = j + dir[k][1];
        if (ti < n && tj < n) dp[ti][tj] = max(dp[ti][tj], dp[i][j]);
      }
    }
  }
  if (dp[n - 1][n - 1] >= 0) {
    for (int i = 0; i < 2 * n - 1; i++) minimum_path[i] = 'a';
  } else {
    int idx = 2 * n - 1 + dp[n - 1][n - 1];
    for (int i = 0; i < idx; i++) minimum_path[i] = 'a';
    for (int i = idx; i < 2 * n - 1; i++) minimum_path[i] = 'z' + 1;
    memset(flag, true, sizeof(flag));
    queue<int> que;
    for (int x = 0; x < n; x++) {
      int y = idx - x;
      if (0 <= y && y < n && dp[x][y] == -1) {
        if (minimum_path[x + y] >= letter_matrix[x][y]) {
          minimum_path[x + y] = letter_matrix[x][y];
          flag[x][y] = false;
          que.push(x * n + y);
        }
      }
    }
    while (!que.empty()) {
      int t = que.front();
      que.pop();
      int x = t / n, y = t % n;
      flag[x][y] = true;
      if (minimum_path[x + y] < letter_matrix[x][y]) continue;
      for (int i = 0; i < dirnum; i++) {
        int tx = x + dir[i][0], ty = y + dir[i][1];
        if (tx < n && ty < n &&
            minimum_path[tx + ty] >= letter_matrix[tx][ty] && flag[tx][ty]) {
          minimum_path[tx + ty] = letter_matrix[tx][ty];
          flag[tx][ty] = false;
          que.push(tx * n + ty);
        }
      }
    }
  }
  minimum_path[2 * n - 1] = '\0';
  printf("%s\n", minimum_path);
}
int main() {
  solve();
  return 0;
}
