#include <bits/stdc++.h>
using namespace std;
long long int powm(long long int x, long long int y,
                   long long int m = 1000000007) {
  x = x % m;
  long long int res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long int modi(long long int a, long long int m = 1000000007) {
  return powm(a, m - 2, m);
}
void pre() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
int32_t main() {
  pre();
  {
    long long int n, k;
    cin >> n >> k;
    string s[n];
    long long int dp[n][n];
    memset(dp, -1, sizeof(dp));
    for (long long int i = 0; i < n; i++) cin >> s[i];
    long long int mx = 0;
    dp[0][0] = (s[0][0] != 'a');
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < n; j++) {
        if (j == 0 && i == 0) continue;
        if (i == 0)
          dp[i][j] = dp[i][j - 1] + (s[i][j] != 'a');
        else if (j == 0)
          dp[i][j] = dp[i - 1][j] + (s[i][j] != 'a');
        else
          dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + (s[i][j] != 'a');
        if (dp[i][j] == k) mx = max(mx, i + j);
      }
    }
    if (dp[n - 1][n - 1] <= k) {
      long long int tp = 2 * n - 1;
      while (tp--) cout << "a";
      return 0;
    }
    queue<pair<long long int, long long int>> q;
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < n; j++) {
        if (dp[i][j] == k && mx == i + j) q.push({i, j});
      }
    }
    long long int kk = mx + 1;
    string as = "";
    if (k != 0)
      while (kk--) as += 'a';
    if (k == 0) {
      q.push({0, 0});
      as += s[0][0];
    }
    while (q.size() > 0) {
      char c = 'z';
      pair<long long int, long long int> l = q.front();
      if (l.first == n - 1 && l.second == n - 1) {
        break;
      }
      vector<pair<long long int, long long int>> v;
      while (q.size() > 0) {
        pair<long long int, long long int> p = q.front();
        q.pop();
        v.push_back(p);
        if (p.first != n - 1) c = min(c, s[p.first + 1][p.second]);
        if (p.second != n - 1) c = min(c, s[p.first][p.second + 1]);
      }
      as += c;
      map<pair<long long int, long long int>, long long int> mp;
      for (long long int i = 0; i < v.size(); i++) {
        long long int f = v[i].first, se = v[i].second;
        if (se != n - 1 && mp[{f, se + 1}] == 0 && s[f][se + 1] == c) {
          q.push({f, se + 1});
          mp[{f, se + 1}]++;
        }
        if (f != n - 1 && mp[{f + 1, se}] == 0 && s[f + 1][se] == c) {
          q.push({f + 1, se});
          mp[{f + 1, se}]++;
        }
      }
    }
    cout << as;
  }
  return 0;
}
