#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long CFMOD = 998244353;
const double PI = 3.14159265358;
const double EPS = 1e-8;
string MIN(string a, string b, bool z_max = false) {
  if (((int)a.size()) == 0 && z_max) return b;
  if (((int)b.size()) == 0 && z_max) return a;
  if (((int)a.size()) < ((int)b.size())) return a;
  if (((int)a.size()) > ((int)b.size())) return b;
  for (int i = 0; i < (((int)a.size())); i++) {
    if (a[i] < b[i]) return a;
    if (a[i] > b[i]) return b;
  }
  return a;
}
void solve() {
  int n, k, mn;
  char fd;
  string ans;
  vector<vector<char>> mat;
  vector<vector<int>> ct;
  vector<vector<bool>> pos;
  vector<vector<string>> str;
  vector<pair<int, int>> v;
  set<pair<int, int>> st;
  cin >> n >> k;
  mat.resize(n + 2);
  str.resize(n + 2);
  ct.resize(n + 2);
  pos.resize(n + 2);
  for (int i = 0; i < (n + 2); i++) {
    mat[i].resize(n + 2);
    str[i].resize(n + 2);
    ct[i].resize(n + 2);
    pos[i].resize(n + 2);
  }
  for (int i = 1; i <= (n); i++)
    for (int j = 1; j <= (n); j++) {
      cin >> mat[i][j];
      ct[i][j] = (mat[i][j] == 'a') + max(ct[i - 1][j], ct[i][j - 1]);
    }
  mn = 0;
  ans = str[1][1];
  for (int i = 1; i <= (n); i++)
    for (int j = 1; j <= (n); j++)
      if ((i + j - 1 - ct[i][j]) <= k) {
        pos[i][j] = true;
        mn = max(mn, i + j - 1);
      }
  for (int i = 1; i <= (n); i++)
    for (int j = 1; j <= (n); j++)
      if ((i + j - 1) == mn && pos[i][j]) {
        if (i < n) v.emplace_back(make_pair(i + 1, j));
        if (j < n) v.emplace_back(make_pair(i, j + 1));
      }
  if (mn == 0) v.emplace_back(make_pair(1, 1));
  for (int i = 1; i <= (n + 1); i++) {
    mat[n + 1][i] = 'z';
    mat[i][n + 1] = 'z';
  }
  for (int i = 0; i < (mn); i++) cout << 'a';
  for (int i = 0; i < (2 * n - 1 - mn); i++) {
    fd = 'z';
    for (auto j : v) fd = min(fd, mat[j.first][j.second]);
    cout << fd;
    for (auto j : v) {
      if (mat[j.first][j.second] == fd) {
        if (j.first < n) st.insert(make_pair(j.first + 1, j.second));
        if (j.second < n) st.insert(make_pair(j.first, j.second + 1));
      }
    }
    v.clear();
    for (auto j : st) v.emplace_back(j);
    st.clear();
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
}
