#include <bits/stdc++.h>
using namespace std;
const int mx = 2005, INF = 1e9;
int dp[mx][mx], mxx;
char s[mx][mx];
char ans[mx * 3];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%s", s[i]);
  }
  for (int i = 1; i <= n; ++i) {
    dp[0][i] = INF;
    dp[i][0] = INF;
  }
  dp[0][1] = 0, dp[1][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (s[i - 1][j - 1] != 'a');
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dp[i][j] <= k) mxx = max(mxx, i + j - 1);
    }
  }
  set<pair<int, int> > v;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if ((dp[i][j] <= k) && (mxx == (i + j - 1))) {
        v.insert({i - 1, j - 1});
      }
    }
  }
  for (int i = 1; i <= mxx; ++i) ans[i - 1] = 'a';
  if (!mxx) v.insert({0, 0}), ans[0] = s[0][0], ++mxx;
  for (int i = mxx + 1; i < (2 * n); ++i) {
    char c = 'z';
    set<pair<int, int> > nw;
    for (pair<int, int> p : v) {
      if ((p.first + 1) < n) c = min(c, s[p.first + 1][p.second]);
      if ((p.second + 1) < n) c = min(c, s[p.first][p.second + 1]);
    }
    ans[i - 1] = c;
    for (pair<int, int> p : v) {
      if ((p.first + 1) < n) {
        if (s[p.first + 1][p.second] == c) nw.insert({p.first + 1, p.second});
      }
      if ((p.second + 1) < n) {
        if (s[p.first][p.second + 1] == c) nw.insert({p.first, p.second + 1});
      }
    }
    v = nw;
  }
  printf("%s\n", ans);
  return 0;
}
