#include <bits/stdc++.h>
const int MAXN = 2000 + 10;
int n, k;
char s[MAXN][MAXN];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s[i] + 1);
  }
  static int f[MAXN][MAXN];
  f[1][1] = s[1][1] != 'a';
  for (int i = 2; i <= n; i++) {
    f[i][1] = f[i - 1][1] + (s[i][1] != 'a');
    f[1][i] = f[1][i - 1] + (s[1][i] != 'a');
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 2; j <= n; j++) {
      f[i][j] = std::min(f[i - 1][j], f[i][j - 1]) + (s[i][j] != 'a');
    }
  }
  std::vector<int> ok;
  int len = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (f[i][j] <= k) {
        if (i + j - 1 > len) {
          len = i + j - 1;
          ok.clear();
          ok.push_back(i);
        } else if (i + j - 1 == len) {
          ok.push_back(i);
        }
      }
    }
  }
  std::vector<int> v;
  static int ord[MAXN][MAXN];
  static int max_next[MAXN][MAXN];
  ord[n][n] = 1;
  for (int x = 2 * n - 1; x >= 2; x--) {
    std::vector<int> v;
    for (int i = 1; i <= n; i++) {
      int j = x - i;
      if (j < 1 || j > n) continue;
      v.push_back(i);
      max_next[i][j] = std::min((i + 1 <= n) ? ord[i + 1][j] : (n + 10),
                                (j + 1 <= n) ? ord[i][j + 1] : (n + 10));
    }
    std::sort(v.begin(), v.end(), [=](int a, int b) {
      return std::make_pair(s[a][x - a], max_next[a][x - a]) <
             std::make_pair(s[b][x - b], max_next[b][x - b]);
    });
    int cnt = 0;
    for (int i : v) {
      ord[i][x - i] = ++cnt;
    }
  }
  if (len == 2 * n - 1) {
    for (int i = 1; i <= len; i++) {
      putchar('a');
    }
    return 0;
  }
  int x, y;
  if (len != 0) {
    int max = 1e9, p = 0;
    for (int i : ok) {
      int j = len + 1 - i;
      if (max > max_next[i][j]) {
        max = max_next[i][j], p = i;
      }
    }
    for (int i = 1; i <= len; i++) {
      putchar('a');
    }
    x = p, y = len + 1 - x;
  } else {
    putchar(s[1][1]);
    len++;
    x = 1, y = 1;
  }
  for (int i = len + 1; i <= 2 * n - 1; i++) {
    if (y == n || (x != n && max_next[x][y] == ord[x + 1][y])) {
      x++;
    } else {
      y++;
    }
    putchar(s[x][y]);
  }
  putchar('\n');
}
