#include <bits/stdc++.h>
using namespace std;
char s[4005];
char c[2005][2005];
int dp[2005][2005];
int ok[2005][2005];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> c[i];
  memset(s, 'z', 2 * n - 1);
  ok[0][0] = 1;
  dp[0][0] = min(k, 2 * n - 1);
  s[0] = dp[0][0] ? 'a' : c[0][0];
  for (int i = 0; i < 2 * n - 2; ++i) {
    for (int x = 0; x <= i; ++x) {
      int y = i - x;
      if (x >= n || y >= n) continue;
      if (!ok[x][y]) continue;
      if (!dp[x][y] && s[i] < c[x][y]) continue;
      if (x + 1 < n) {
        ok[x + 1][y] = 1;
        dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] - (c[x][y] != 'a'));
        s[i + 1] = min(s[i + 1], dp[x + 1][y] ? 'a' : c[x + 1][y]);
      }
      if (y + 1 < n) {
        ok[x][y + 1] = 1;
        dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] - (c[x][y] != 'a'));
        s[i + 1] = min(s[i + 1], dp[x][y + 1] ? 'a' : c[x][y + 1]);
      }
    }
  }
  cout << s;
}
