#include <bits/stdc++.h>
using namespace std;
const double DINF = numeric_limits<double>::infinity();
const long long MOD = 1e9 + 7;
const double EPS = 1e-7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<long long> rd_;
long long randomll() { return rd_(mmtw_); }
long long rnd(long long x, long long y) { return rd_(mmtw_) % (y - x + 1) + x; }
const int MAXN = 2e3 + 5;
int n, k;
char a[MAXN][MAXN];
int dp[MAXN][MAXN];
const int inf = 1e7;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i + 1][j + 1];
    }
  }
  for (int i = 0; i < n + 1; ++i) {
    for (int j = 0; j < n + 1; ++j) {
      dp[i][j] = inf + 10;
    }
  }
  string second;
  dp[1][1] = 0;
  second.push_back(a[1][1]);
  if (a[1][1] != 'a' && k != 0) {
    dp[1][1] = 1;
    second = "a";
  }
  for (int row = 1; row < 2 * n - 1; ++row) {
    for (char ch = 'a'; ch <= 'z'; ++ch) {
      bool isset = false;
      for (int i = row + 1, j = 1; i >= 1; --i, ++j) {
        if (i > n || j > n) continue;
        if (a[i][j] == ch && min(dp[i - 1][j], dp[i][j - 1]) < inf) {
          isset = true;
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
        } else {
          if (min(dp[i - 1][j], dp[i][j - 1]) < k) {
            isset = true;
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
          }
        }
      }
      if (isset) {
        second.push_back(ch);
        break;
      }
    }
  }
  cout << second << endl;
}
