#include <bits/stdc++.h>
using namespace std;
const int nmax = 2048;
const int INF = 1e9 + 1e8 + 1e7 + 1e6 + 1e5 + 1e4 + 1e3 + 1e2 + 1e1;
char grid[nmax][nmax];
int dp[nmax][nmax];
inline void minn(int& a, int b) { a = min(a, b); }
inline void maxx(int& a, int b) { a = max(a, b); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, k;
  auto inside = [&](int row, int col) {
    return 0 <= row && 0 <= col && row < n && col < n;
  };
  cin >> n >> k;
  for (int row = 0; row < n; ++row) cin >> grid[row];
  for (int row = 0; row < n; ++row)
    for (int col = 0; col < n; ++col) dp[row][col] = INF;
  dp[0][0] = 0;
  for (int row = 0; row < n; ++row)
    for (int col = 0; col < n; ++col) {
      if (row != 0) minn(dp[row][col], dp[row - 1][col]);
      if (col != 0) minn(dp[row][col], dp[row][col - 1]);
      if (grid[row][col] != 'a') ++dp[row][col];
    }
  int pref = 0;
  for (int row = 0; row < n; ++row)
    for (int col = 0; col < n; ++col)
      if (dp[row][col] <= k) maxx(pref, row + col + 1);
  string answer(pref, 'a');
  vector<pair<int, int> > L;
  for (int row = 0; row < n; ++row)
    for (int col = 0; col < n; ++col)
      if (dp[row][col] <= k && row + col + 1 == pref) L.emplace_back(row, col);
  if (L.empty()) {
    L.emplace_back(0, 0);
    answer += grid[0][0];
  }
  while (!L.empty()) {
    char best_char = 'z';
    vector<pair<int, int> > new_list;
    for (pair<int, int> p : L)
      for (int d_row : {0, 1}) {
        int d_col = 1 - d_row, r2 = p.first + d_row, c2 = p.second + d_col;
        if (inside(r2, c2))
          if (grid[r2][c2] <= best_char) {
            if (grid[r2][c2] < best_char) {
              new_list.clear();
              best_char = grid[r2][c2];
            }
            new_list.emplace_back(r2, c2);
          }
      }
    if (new_list.empty()) break;
    answer += best_char;
    L = new_list;
    sort(L.begin(), L.end());
    L.resize(unique(L.begin(), L.end()) - L.begin());
  }
  cout << answer;
}
