#include <bits/stdc++.h>
using namespace std;
char a[2222][2222];
int mn[2222][2222];
int check[2222][2222];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%s", a[i]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      mn[i][j] = 1011111111;
    }
  }
  mn[0][0] = 0;
  for (int i = 0; i <= 2 * n - 2; i++) {
    for (int j = 0; j < n; j++) {
      if (i - j < 0 || i - j >= n) continue;
      mn[j][i - j] += a[j][i - j] != 'a';
      mn[j + 1][i - j] = min(mn[j + 1][i - j], mn[j][i - j]);
      mn[j][i - j + 1] = min(mn[j][i - j + 1], mn[j][i - j]);
    }
  }
  int mx = -1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (mn[i][j] <= k) mx = max(mx, i + j);
    }
  }
  for (int i = 0; i <= mx; i++) printf("a");
  if (mx != -1) {
    for (int i = 0; i < n; i++) {
      if (mx - i < 0 || mx - i >= n) continue;
      if (mn[i][mx - i] <= k) {
        check[i + 1][mx - i] = 1;
        check[i][mx - i + 1] = 1;
      }
    }
  } else
    check[0][0] = 1;
  for (int i = mx + 1; i <= 2 * n - 2; i++) {
    char tmn = 'z';
    for (int j = 0; j < n; j++) {
      if (i - j < 0 || i - j >= n) continue;
      if (check[j][i - j]) tmn = min(tmn, a[j][i - j]);
    }
    printf("%c", tmn);
    for (int j = 0; j < n; j++) {
      if (i - j < 0 || i - j >= n) continue;
      if (check[j][i - j] && a[j][i - j] == tmn) {
        check[j][i - j + 1] = 1;
        check[j + 1][i - j] = 1;
      }
    }
  }
}
