#include <bits/stdc++.h>
using namespace std;
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, k;
  cin >> n >> k;
  vector<string> s(n);
  for (long long i = 0; i < n; i++) cin >> s[i];
  vector<long long> g[n * n];
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++) {
      if (i + 1 < n) g[i * n + j].push_back((i + 1) * n + j);
      if (j + 1 < n) g[i * n + j].push_back(i * n + (j + 1));
    }
  vector<long long> kval(n * n);
  vector<char> cval(n * n);
  vector<char> cval2(n * n);
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++) {
      cval[i * n + j] = s[i][j];
      cval2[i * n + j] = s[i][j];
    }
  kval[0] = k;
  if (cval[0] != 'a' && kval[0]) {
    cval[0] = 'a';
    kval[0] -= 1;
  }
  string ans;
  queue<long long> q;
  ans += cval[0];
  q.push(0);
  while (q.size()) {
    set<long long> tq;
    long long maxkval = 0;
    char mincval = 'z';
    while (q.size()) {
      long long x = q.front();
      q.pop();
      for (auto y : g[x]) {
        tq.insert(y);
        if (kval[x]) {
          kval[y] = max(kval[y], kval[x] - (cval[y] != 'a'));
          cval2[y] = 'a';
        }
        maxkval = max(maxkval, kval[y]);
        mincval = min(mincval, cval2[y]);
      }
    }
    ans += mincval;
    for (auto v : tq)
      if (cval2[v] == mincval) q.push(v);
  }
  cout << ans.substr(0, 2 * n - 1) << '\n';
}
