#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
char a[2009][2009];
int dp[2009][2009];
bool used[2009][2009];
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  scanf("\n");
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%c", &a[i][j]);
    }
    scanf("\n");
  }
  int max_cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int cur_min = 1e9;
      if (i - 1 >= 0) cur_min = min(cur_min, dp[i - 1][j]);
      if (j - 1 >= 0) cur_min = min(cur_min, dp[i][j - 1]);
      if (a[i][j] != 'a') cur_min++;
      dp[i][j] = cur_min % (int)1e9;
      if (dp[i][j] <= k && i + j + 1 > max_cnt) max_cnt = i + j + 1;
    }
  }
  string ans = "";
  for (int i = 0; i < max_cnt; i++) ans += 'a';
  vector<pair<int, int> > list;
  if (max_cnt == 0) {
    list.push_back(make_pair(0, 0));
    ans += a[0][0];
  } else {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i + j + 1 == max_cnt && dp[i][j] <= k)
          list.push_back(make_pair(i, j));
      }
    }
  }
  while (ans.size() != 2 * n - 1) {
    vector<pair<int, int> > cur_list;
    char c = 'z';
    for (int i = 0; i < list.size(); i++) {
      int ii = list[i].first, jj = list[i].second;
      if (ii + 1 < n && a[ii + 1][jj] < c) c = a[ii + 1][jj];
      if (jj + 1 < n && a[ii][jj + 1] < c) c = a[ii][jj + 1];
    }
    ans += c;
    for (int i = 0; i < list.size(); i++) {
      int ii = list[i].first, jj = list[i].second;
      if (ii + 1 < n && a[ii + 1][jj] == c && !used[ii + 1][jj]) {
        cur_list.push_back(make_pair(ii + 1, jj));
        used[ii + 1][jj] = true;
      }
      if (jj + 1 < n && a[ii][jj + 1] == c && !used[ii][jj + 1]) {
        cur_list.push_back(make_pair(ii, jj + 1));
        used[ii][jj + 1] = true;
      }
    }
    list = cur_list;
  }
  printf("%s", ans.c_str());
}
