#include <bits/stdc++.h>
using namespace std;
int n, m, sum = -1;
char s[4005][4005];
bool vis[4005][4005];
int pre[4005][4005];
vector<pair<int, int> > q, temp;
void bfs() {
  for (int t = sum; t < 2 * n; t++) {
    int x, y;
    char c0 = 'z';
    for (int k = 0; k < q.size(); k++) {
      x = q[k].first;
      y = q[k].second;
      if (x + 1 <= n && s[x + 1][y] < c0) c0 = s[x + 1][y];
      if (y + 1 <= n && s[x][y + 1] < c0) c0 = s[x][y + 1];
    }
    for (int k = 0; k < q.size(); k++) {
      x = q[k].first;
      y = q[k].second;
      if (x + 1 <= n && s[x + 1][y] == c0 && !vis[x + 1][y]) {
        vis[x + 1][y] = 1;
        pre[x + 1][y] = 1;
        temp.push_back(make_pair(x + 1, y));
      }
      if (y + 1 <= n && s[x][y + 1] == c0 && !vis[x][y + 1]) {
        vis[x][y + 1] = 1;
        pre[x][y + 1] = 0;
        temp.push_back(make_pair(x, y + 1));
      }
    }
    swap(q, temp);
    temp.clear();
  }
}
int dp[4005][4005];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> s[i] + 1;
  }
  memset(dp, 1, sizeof(dp));
  dp[1][1] = (s[1][1] != 'a');
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i > 1 || j > 1)
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + (s[i][j] != 'a');
      if (dp[i][j] <= m && i + j > sum) {
        sum = i + j;
      }
    }
  }
  cerr << "sum = " << sum << endl;
  if (sum == -1) {
    q.push_back(make_pair(1, 1));
  } else {
    for (int i = 1; i <= n; i++) {
      int j = sum - i;
      if (dp[i][j] <= m) q.push_back(make_pair(i, j));
    }
  }
  bfs();
  vector<char> vec;
  int x = n, y = n;
  while (x + y > sum && x > 0 && y > 0) {
    vec.push_back(s[x][y]);
    if (pre[x][y])
      --x;
    else
      --y;
  }
  for (int k = 1; k < sum; k++) cout << 'a';
  for (int k = vec.size() - 1; k >= 0; k--) cout << vec[k];
  return 0;
}
