#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;
const int MAXN = 5e5 + 5;
const int MOD = 1e9 + 7;
bool isvalid(long long x, long long y, long long n, long long m) {
  x--;
  y--;
  if (x > -1 && x < n)
    if (y > -1 && y < m) return 1;
  return 0;
}
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(NULL);
  long long t;
  t = 1;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    vector<string> mat(n + 1);
    for (int i = 0; i < (int)(n); i++) {
      cin >> mat[i + 1];
    }
    vector<vector<long long> > dp(n + 1, vector<long long>(n + 1));
    vector<pair<long long, long long> > ho;
    k = min(2 * n - 1, k);
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        if (mat[i][j - 1] == 'a') dp[i][j] += 1;
        if (i + j - 1 - dp[i][j] <= k) ho.push_back({i + j, j});
      }
    }
    ho.push_back({1, 0});
    sort(ho.rbegin(), ho.rend());
    queue<pair<long long, long long> > opfront;
    set<pair<long long, long long> > unique;
    int minchar = 'z';
    for (int i = 0; i < ho.size(); i++) {
      if (ho[i].first == ho[0].first) {
        opfront.push({ho[i].first - ho[i].second, ho[i].second});
        if (isvalid(ho[i].first - ho[i].second, ho[i].second + 1, n, n))
          minchar =
              min(mat[ho[i].first - ho[i].second][ho[i].second], (char)minchar);
        if (isvalid(ho[i].first - ho[i].second + 1, ho[i].second, n, n))
          minchar = min(mat[ho[i].first - ho[i].second + 1][ho[i].second - 1],
                        (char)minchar);
      }
    }
    string ans = "";
    for (int i = 1; i < ho[0].first; i++) ans += 'a';
    pair<long long, long long> cho;
    int help;
    while (!opfront.empty() &&
           (opfront.front().first != n || opfront.front().second != n)) {
      unique.clear();
      help = 'z';
      while (!opfront.empty()) {
        cho = opfront.front();
        opfront.pop();
        if (isvalid(cho.first + 1, cho.second, n, n)) {
          unique.insert({cho.first + 1, cho.second});
          help = min((char)help, mat[cho.first + 1][cho.second - 1]);
        }
        if (isvalid(cho.first, cho.second + 1, n, n)) {
          unique.insert({cho.first, cho.second + 1});
          help = min((char)help, mat[cho.first][cho.second]);
        }
      }
      for (auto itr = unique.begin(); itr != unique.end(); ++itr) {
        if (mat[(*itr).first][(*itr).second - 1] == help) {
          opfront.push(*itr);
        }
      }
      minchar = help;
      ans += minchar;
    }
    cout << ans << "\n";
  }
}
