#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long powe(long long x, long long y) {
  x = x % mod, y = y % (mod - 1);
  long long ans = 1;
  while (y > 0) {
    if (y & 1) {
      ans = (1ll * x * ans) % mod;
    }
    y >>= 1;
    x = (1ll * x * x) % mod;
  }
  return ans;
}
void fun() {}
const long long N = 2002;
long long book[N][N];
long long dp[N][N];
string s[N];
void solve() {
  long long n, k;
  cin >> n >> k;
  for (long long i = 0; i < n; i++) {
    cin >> s[i];
  }
  long long mx = 0;
  for (long long i = 0; i <= n; i++) {
    dp[i][0] = INT_MAX;
    dp[0][i] = INT_MAX;
  }
  dp[0][1] = 0;
  dp[1][0] = 0;
  book[1][1] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      dp[i][j] = INT_MAX;
      if (dp[i - 1][j] >= k && dp[i][j - 1] >= k && s[i - 1][j - 1] != 'a')
        continue;
      if (s[i - 1][j - 1] == 'a') {
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
      } else if (dp[i - 1][j] < k || dp[i][j - 1] < k) {
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
      }
      if (dp[i][j] <= k) {
        mx = max(mx, (i + j - 1));
        book[i + 1][j] = 1;
        book[i][j + 1] = 1;
      }
    }
  }
  long long cnt = 0;
  while (cnt != mx) {
    cout << 'a';
    cnt++;
  }
  for (long long x = mx + 1; x <= 2 * n - 1; x++) {
    char mn = 'z';
    for (long long j = 1; j <= n; j++) {
      long long i = x - j + 1;
      if (i < 1 || i > n) continue;
      if (book[i][j]) {
        mn = min(mn, s[i - 1][j - 1]);
      }
    }
    for (long long j = 1; j <= n; j++) {
      long long i = x - j + 1;
      if (i < 1 || i > n) continue;
      if (book[i][j] && s[i - 1][j - 1] == mn) {
        book[i + 1][j] = 1;
        book[i][j + 1] = 1;
      }
    }
    cout << mn;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
