#include <bits/stdc++.h>
using namespace std;
const int maxn = 2123;
char mat[maxn][maxn];
int dp[maxn][maxn], n, k;
inline bool inside(int x, int y) { return x > 0 && y > 0 && x <= n && y <= n; }
int main() {
  scanf("%d%d", &n, &k);
  for (int(i) = (1); (i) <= (n); (i)++) scanf("%s", mat[i] + 1);
  dp[1][1] = (mat[1][1] > 'a');
  for (int(i) = (2); (i) <= (n); (i)++) {
    dp[1][i] = dp[1][i - 1] + (mat[1][i] > 'a');
    dp[i][1] = dp[i - 1][1] + (mat[i][1] > 'a');
  }
  for (int(i) = (2); (i) <= (n); (i)++)
    for (int(j) = (2); (j) <= (n); (j)++)
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (mat[i][j] > 'a');
  set<pair<int, int> > ans;
  ans.insert(make_pair(0, 1));
  int now = 0;
  for (int(i) = (1); (i) <= (n); (i)++)
    for (int(j) = (1); (j) <= (n); (j)++) {
      if (dp[i][j] > k) continue;
      if (i + j - 1 == now)
        ans.insert(make_pair(i, j));
      else if (i + j - 1 > now) {
        ans.clear();
        ans.insert(make_pair(i, j));
        now = i + j - 1;
      }
    }
  for (int(i) = (0); (i) <= ((now)-1); (i)++) putchar('a');
  if (now == 2 * n - 1) return 0;
  for (int(i) = (0); (i) <= ((2 * n - 1 - now) - 1); (i)++) {
    set<pair<int, int> > cur;
    char tmp = 'z' + 1;
    for (auto it : ans) {
      int x = it.first, y = it.second;
      if (inside(x + 1, y)) {
        if (mat[x + 1][y] < tmp) {
          tmp = mat[x + 1][y];
          cur.clear();
          cur.insert(make_pair(x + 1, y));
        } else if (mat[x + 1][y] == tmp)
          cur.insert(make_pair(x + 1, y));
      }
      if (inside(x, y + 1)) {
        if (mat[x][y + 1] < tmp) {
          tmp = mat[x][y + 1];
          cur.clear();
          cur.insert(make_pair(x, y + 1));
        } else if (mat[x][y + 1] == tmp)
          cur.insert(make_pair(x, y + 1));
      }
    }
    putchar(tmp);
    swap(ans, cur);
  }
  return 0;
}
