#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, k, dp[N][N];
string str[N];
set<pair<int, int>> st, st1;
string ans = "";
void mini(int &a, int b) { a = min(a, b); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> str[i];
  for (int i = 1; i <= n; i++) str[i] = '_' + str[i];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++) dp[i][j] = 1e9;
  dp[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      mini(dp[i][j], dp[i - 1][j]);
      mini(dp[i][j], dp[i][j - 1]);
      if (str[i][j] != 'a') dp[i][j]++;
    }
  }
  int mx = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if ((dp[i][j] <= k) && (i + j) > mx) mx = i + j;
  for (int i = 1; i <= mx - 1; i++) ans += 'a';
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i + j == mx && dp[i][j] <= k) st.insert({i, j});
  if (st.empty()) {
    st.insert({1, 1});
    ans += str[1][1];
  }
  bool mark = false;
  while (!st.empty()) {
    char ch = 'z' + 1;
    for (auto it : st) {
      if (it.first < n && it.second <= n)
        ch = min(ch, str[it.first + 1][it.second]);
      if (it.first <= n && it.second < n)
        ch = min(ch, str[it.first][it.second + 1]);
    }
    if (ch == 'z' + 1) break;
    ans += ch;
    for (auto it : st) {
      if (it.first < n && it.second <= n)
        if (str[it.first + 1][it.second] == ch)
          st1.insert({it.first + 1, it.second});
      if (it.first <= n && it.second < n)
        if (str[it.first][it.second + 1] == ch)
          st1.insert({it.first, it.second + 1});
    }
    st = st1;
    st1.clear();
  }
  cout << ans << "\n";
}
