#include <bits/stdc++.h>
using namespace std;
template <class n, class second>
ostream &operator<<(ostream &p, pair<n, second> x) {
  return p << "<" << x.first << ", " << x.second << ">";
}
template <class n>
auto operator<<(ostream &p, n y) ->
    typename enable_if<!is_same<n, string>::value,
                       decltype(y.begin(), p)>::type {
  int o = 0;
  p << "{";
  for (auto c : y) {
    if (o++) p << ", ";
    p << c;
  }
  return p << "}";
}
void dor() { cerr << '\n'; }
template <class n, class... second>
void dor(n p, second... y) {
  cerr << p << " ";
  dor(y...);
}
template <class n, class second>
void mini(n &p, second y) {
  if (p > y) p = y;
}
template <class n, class second>
void maxi(n &p, second y) {
  if (p < y) p = y;
}
const int MXN = 2005;
char in[MXN][MXN];
int dpa[MXN][MXN];
int n, k;
bool added[MXN][MXN];
pair<int, int> slkfsdkf[MXN][MXN];
int kol[MXN][MXN];
int KOL = 1;
void go(vector<pair<int, int>> starts) {
  vector<pair<pair<int, int>, pair<int, int>>> starts2;
  while (starts.size()) {
    ;
    for (auto i : starts) {
      for (int j = 0; j < (int)(2); ++j) {
        int nx = i.first + (j == 0);
        int ny = i.second + (j == 1);
        if (nx > n || ny > n || ny < 1 || nx < 1 || added[nx][ny]) continue;
        slkfsdkf[nx][ny] = i;
        added[nx][ny] = 1;
        starts2.push_back(
            make_pair(make_pair(kol[i.first][i.second], (int)in[nx][ny]),
                      make_pair(nx, ny)));
      }
    }
    starts.clear();
    sort((starts2).begin(), (starts2).end());
    pair<int, int> slkfsdkf = make_pair(-1, -1);
    for (auto i : starts2) {
      kol[i.second.first][i.second.second] = (KOL += (slkfsdkf != i.first));
      slkfsdkf = i.first;
      starts.push_back(i.second);
    }
    starts2.clear();
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = (1); i <= (int)(n); ++i)
    for (int j = (1); j <= (int)(n); ++j) {
      scanf(" %c", &in[i][j]);
    }
  for (int i = (0); i <= (int)(n); ++i)
    for (int j = (0); j <= (int)(n); ++j) dpa[i][j] = 1e9;
  dpa[0][1] = dpa[1][0] = 0;
  for (int i = (1); i <= (int)(n); ++i)
    for (int j = (1); j <= (int)(n); ++j) {
      dpa[i][j] = min(dpa[i - 1][j], dpa[i][j - 1]) + (in[i][j] != 'a');
    }
  int mx = 0;
  for (int i = (0); i <= (int)(n); ++i) {
    for (int j = (0); j <= (int)(n); ++j) {
      if (dpa[i][j] <= k) maxi(mx, i + j);
    }
  }
  if (mx == n + n) {
    for (int i = 0; i < (int)(2 * n - 1); ++i) putchar('a');
    cout << '\n';
    return 0;
  }
  vector<pair<int, int>> starts;
  for (int i = (0); i <= (int)(n); ++i) {
    for (int j = (0); j <= (int)(n); ++j) {
      if (dpa[i][j] <= k && i + j == mx) {
        starts.push_back({i, j});
        in[i][j] = 'a';
      }
    }
  }
  go(starts);
  string ans1;
  for (int i = 0; i < (int)(mx - 1); ++i) ans1 += 'a';
  string ans2;
  pair<int, int> end = make_pair(n, n);
  int II = 0;
  while (end.first + end.second != mx) {
    if (II > 1e7) assert(false);
    II++;
    ans2.push_back(in[end.first][end.second]);
    end = slkfsdkf[end.first][end.second];
  }
  reverse((ans2).begin(), (ans2).end());
  ans1 = ans1 + ans2;
  cout << ans1 << '\n';
}
