#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int inf = INT_MAX;
const long long mod = 1e9 + 7;
const int pi = acos(-1);
const int dx[4] = {0, 1, 0, 0};
const int dy[4] = {1, 0, 0, 0};
const int N = 2e3 + 5;
int dp[N][N];
char c[N][N];
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie();
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    c[i][n + 1] = 'z' + 1;
    c[n + 1][i] = 'z' + 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (j == 1)
        dp[i][j] = dp[i - 1][j];
      else if (i == 1)
        dp[i][j] = dp[i][j - 1];
      else
        dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]);
      dp[i][j] += (c[i][j] != 'a');
    }
  }
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dp[i][j] <= k) mx = max(mx, i + j - 1);
    }
  }
  set<pair<int, int> > v;
  if (mx == 0) {
    cout << c[1][1];
    v.insert(make_pair(1, 1));
  } else {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (dp[i][j] == k && i + j - 1 == mx) v.insert(make_pair(i, j));
      }
    }
  }
  for (int i = 1; i <= mx; i++) cout << 'a';
  while (1) {
    char mn = 'z' + 1;
    for (set<pair<int, int> >::iterator it = v.begin(); it != v.end(); it++) {
      pair<int, int> p = *it;
      mn = min(mn, c[p.first + 1][p.second]);
      mn = min(mn, c[p.first][p.second + 1]);
    }
    if (mn > 'z') break;
    cout << mn;
    set<pair<int, int> > second;
    for (set<pair<int, int> >::iterator it = v.begin(); it != v.end(); it++) {
      pair<int, int> p = *it;
      if (c[p.first + 1][p.second] == mn)
        second.insert(make_pair(p.first + 1, p.second));
      if (c[p.first][p.second + 1] == mn)
        second.insert(make_pair(p.first, p.second + 1));
    }
    v = second;
  }
}
