#include <bits/stdc++.h>
using namespace std;
int n, k, mx[2005][2005], maxA;
char mp[2005][2005];
bool vis[2005][2005];
queue<pair<int, int> > q, s;
inline void dfs(int x, int y, int dep) {
  if (~mx[x][y]) return;
  if (x == 1 && y == 1)
    mx[x][y] = (mp[x][y] == 'a');
  else {
    if (x ^ 1) dfs(x - 1, y, dep - 1);
    if (y ^ 1) dfs(x, y - 1, dep - 1);
    mx[x][y] = (mp[x][y] == 'a') + max(mx[x - 1][y], mx[x][y - 1]);
  }
  if (dep < maxA) return;
  if (mx[x][y] >= dep - k) {
    if (dep == maxA)
      q.push(make_pair(x, y));
    else if (dep > maxA) {
      while (!q.empty()) q.pop();
      q.push(make_pair(x, y)), maxA = dep;
    }
  }
}
int main() {
  memset(mx, -1, sizeof(mx)), scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
  maxA = k;
  dfs(n, n, n * 2 - 1);
  int sig = 26;
  string tmp;
  for (int i = 1; i <= min(maxA, n * 2 - 1); ++i) tmp = tmp + 'a';
  if (maxA >= n * 2 - 1) return cout << tmp, 0;
  if (!maxA) q.push(make_pair(1, 1)), tmp = tmp + mp[1][1];
  for (int i = maxA ? maxA + 1 : 2; i <= n * 2 - 1; ++i) {
    sig = 26;
    while (!q.empty()) {
      pair<int, int> t = q.front();
      q.pop();
      int x = t.first, y = t.second, i, j;
      i = x + 1, j = y;
      if (i <= n && !vis[i][j]) {
        vis[i][j] = 1;
        if (mp[i][j] - 'a' == sig)
          s.push(make_pair(i, j));
        else if (mp[i][j] - 'a' < sig) {
          while (!s.empty()) s.pop();
          s.push(make_pair(i, j)), sig = mp[i][j] - 'a';
        }
      }
      i = x, j = y + 1;
      if (j <= n && !vis[i][j]) {
        vis[i][j] = 1;
        if (mp[i][j] - 'a' == sig)
          s.push(make_pair(i, j));
        else if (mp[i][j] - 'a' < sig) {
          while (!s.empty()) s.pop();
          s.push(make_pair(i, j)), sig = mp[i][j] - 'a';
        }
      }
    }
    tmp = tmp + (char)(sig + 'a');
    while (!s.empty()) q.push(s.front()), s.pop();
  }
  cout << tmp;
  return 0;
}
