#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
char a[N][N];
int dp[N][N];
bool vis[N][N];
int n, k;
queue<int> q1, q2;
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
  memset(dp, 0, sizeof(dp));
  int MAX = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      if (i > 1 && j > 1)
        dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]);
      else if (i > 1)
        dp[i][j] = dp[i - 1][j];
      else if (j > 1)
        dp[i][j] = dp[i][j - 1];
      dp[i][j] += (a[i][j] == 'a' ? 0 : 1);
      if (dp[i][j] <= k) MAX = max(MAX, i + j - 1);
    }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (dp[i][j] <= k && MAX == i + j - 1) {
        q1.push(i);
        q1.push(j);
      }
  string ans = "";
  for (int i = 1; i <= MAX; ++i) ans += "a";
  if (!MAX) {
    q1.push(1);
    q1.push(1);
    ans += a[1][1];
    MAX = 1;
  }
  for (int i = MAX + 1; i <= 2 * n - 1; ++i) {
    q2 = q1;
    char res = 'z';
    while (!q1.empty()) {
      int x = q1.front();
      q1.pop();
      int y = q1.front();
      q1.pop();
      if (x + 1 <= n) res = min(res, a[x + 1][y]);
      if (y + 1 <= n) res = min(res, a[x][y + 1]);
    }
    ans += res;
    while (!q2.empty()) {
      int x = q2.front();
      q2.pop();
      int y = q2.front();
      q2.pop();
      if (x + 1 <= n && !vis[x + 1][y] && a[x + 1][y] == res) {
        vis[x + 1][y] = true;
        q1.push(x + 1);
        q1.push(y);
      }
      if (y + 1 <= n && !vis[x][y + 1] && a[x][y + 1] == res) {
        vis[x][y + 1] = true;
        q1.push(x);
        q1.push(y + 1);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}
