#include <bits/stdc++.h>
using namespace std;
long long INF = INT_MAX;
long long mod = 1000000007;
bool good(int i, int j, int n) { return i >= 0 && j >= 0 && i < n && j < n; }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  char a[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) cin >> a[i][j];
  }
  int dp[n][n];
  dp[0][0] = 0;
  if (a[0][0] != 'a') dp[0][0]++;
  for (int i = 1; i < n; i++) {
    if (a[i][0] == 'a')
      dp[i][0] = dp[i - 1][0];
    else
      dp[i][0] = dp[i - 1][0] + 1;
  }
  for (int i = 1; i < n; i++) {
    if (a[0][i] == 'a')
      dp[0][i] = dp[0][i - 1];
    else
      dp[0][i] = dp[0][i - 1] + 1;
  }
  for (int j = 1; j < n; j++) {
    for (int i = 1; i < n; i++) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
      if (a[i][j] != 'a') {
        dp[i][j]++;
      }
    }
  }
  int ii = 0;
  int jj = 0;
  for (int j = 0; j < n; j++) {
    for (int i = 0; i < n; i++) {
      if (dp[i][j] <= k && i + j > ii + jj) {
        ii = i;
        jj = j;
      }
    }
  }
  vector<pair<int, int>> from;
  for (int j = 0; j < n; j++) {
    for (int i = 0; i < n; i++) {
      if (dp[i][j] <= k && i + j == ii + jj) {
        from.push_back({i, j});
      }
    }
  }
  string answer(ii + jj + 1, 'a');
  int diag = ii + jj + 1;
  if (dp[0][0] == 1 && k == 0) {
    diag--;
    answer = "";
    answer += a[0][0];
    from.clear();
    from.push_back({0, 0});
  }
  while (!from.empty()) {
    char best_char = 'z';
    vector<pair<int, int>> new_list;
    for (pair<int, int> t : from) {
      for (int dx = 0; dx < 2; dx++) {
        int dy = 1 - dx;
        int x = dx + t.first;
        int y = dy + t.second;
        if (good(x, y, n)) {
          if (a[x][y] <= best_char) {
            if (a[x][y] < best_char) {
              new_list.clear();
            }
            best_char = a[x][y];
            new_list.push_back({x, y});
          }
        }
      }
    }
    if (new_list.empty()) break;
    answer += best_char;
    from = new_list;
    sort(from.begin(), from.end());
    from.resize(unique(from.begin(), from.end()) - from.begin());
  }
  cout << answer << "\n";
}
