#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  string mat[n + 5];
  int dp[n + 5][n + 5];
  for (int i = 0; i < (n); i++) cin >> mat[i];
  memset(dp, 0, sizeof(dp));
  if (mat[0][0] == 'a') dp[0][0] = 1;
  for (int i = 1; i < (n); i++) {
    dp[i][0] = dp[i - 1][0];
    if (mat[i][0] == 'a') dp[i][0]++;
    dp[0][i] = dp[0][i - 1];
    if (mat[0][i] == 'a') dp[0][i]++;
  }
  for (int i = 1; i < (n); i++) {
    for (int j = 1; j < (n); j++) {
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      if (mat[i][j] == 'a') dp[i][j]++;
    }
  }
  int maxi = -1;
  for (int i = 0; i < (n); i++) {
    for (int j = 0; j < (n); j++) {
      if (i + j + 1 - dp[i][j] - k <= 0) maxi = max(maxi, i + j);
    }
  }
  set<pair<int, int>> pts;
  if (maxi == -1)
    pts.insert(make_pair(0, 0));
  else {
    for (int i = 0; i < (n); i++) {
      for (int j = 0; j < (n); j++) {
        if (i + j == maxi && (i + j + 1 - dp[i][j] - k) == 0) {
          pts.insert(make_pair(i, j));
        }
      }
    }
  }
  string ans, cont;
  for (int i = 0; i < (maxi + 1); i++) ans.push_back('a');
  if (maxi == -1) ans.push_back(mat[0][0]), maxi++;
  for (int i = maxi; i < (2 * n - 2); i++) {
    char mini = 'z' + 1;
    for (auto x : pts) {
      int r = x.first, c = x.second;
      if (r < n - 1) mini = min(mini, mat[r + 1][c]);
      if (c < n - 1) mini = min(mini, mat[r][c + 1]);
    }
    ans.push_back(mini);
    set<pair<int, int>> temp;
    for (auto x : pts) {
      int r = x.first, c = x.second;
      if (r < n - 1) {
        if (mat[r + 1][c] == mini) temp.insert(make_pair(r + 1, c));
      }
      if (c < n - 1) {
        if (mat[r][c + 1] == mini) temp.insert(make_pair(r, c + 1));
      }
    }
    pts = temp;
  }
  cout << ans;
}
