#include <bits/stdc++.h>
using namespace std;
void err() { cerr << "\033[39;0m" << endl; }
template <template <typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
  for (auto x : a) cerr << x << ' ';
  err(args...);
}
template <typename T, typename... Args>
void err(T a, Args... args) {
  cerr << a << ' ';
  err(args...);
}
int n, k;
char s[2005][2005];
int cnt[2005][2005];
bool vis[2005][2005];
bool out(const int &x, const int &y) { return x < 1 || x > n; }
void relax(int x, int y) {
  int ux = x - 1, uy = y;
  int lx = x, ly = y - 1;
  if (out(ux, uy))
    cnt[x][y] = cnt[lx][ly] + (s[x][y] == 'a');
  else if (out(lx, ly))
    cnt[x][y] = cnt[ux][uy] + (s[x][y] == 'a');
  else
    cnt[x][y] = max(cnt[lx][ly], cnt[ux][uy]) + (s[x][y] == 'a');
}
bool ok(int x, int y) { return !out(x, y) && vis[x][y]; }
void update(int x, int y) {
  int ux = x - 1, uy = y;
  int lx = x, ly = y - 1;
  if (ok(ux, uy) || ok(lx, ly)) {
    vis[x][y] = 1;
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
  cnt[1][1] = s[1][1] == 'a';
  vector<pair<int, int> > v;
  for (int i = 1; i < n + n; ++i)
    for (int r = 1; r <= n && r <= i; ++r) {
      int c = i - r + 1;
      ;
      if (c > n) continue;
      if (i > 1) relax(r, c);
      ;
      if (i - cnt[r][c] <= k) {
        if (v.size() && v[0].first + v[0].second < r + c) v.clear();
        if (v.empty() || r + c == v[0].first + v[0].second)
          v.emplace_back(r, c);
      }
    }
  for (auto &p : v) {
    vis[p.first][p.second] = 1;
    ;
  }
  int f = v.size() ? v[0].first + v[0].second - 1 : 0;
  string res(f, 'a');
  if (!f) res.push_back(s[1][1]), ++f, vis[1][1] = 1;
  if (f == n + n - 1) {
    cout << res << endl;
    return 0;
  }
  for (int i = f + 1; i < n + n; ++i) {
    vector<pair<int, int> > v;
    for (int r = 1; r <= n && r <= i; ++r) {
      int c = i - r + 1;
      if (c > n) continue;
      update(r, c);
      if (vis[r][c]) {
        if (v.size() && s[v[0].first][v[0].second] > s[r][c]) {
          int x, y;
          while (v.size()) {
            tie(x, y) = v.back();
            vis[x][y] = 0;
            v.pop_back();
          }
        }
        if (v.empty() || s[r][c] == s[v[0].first][v[0].second]) {
          v.emplace_back(r, c);
          ;
        } else {
          vis[r][c] = 0;
        }
      }
    };
    res.push_back(s[v[0].first][v[0].second]);
    ;
  }
  cout << res << endl;
  return 0;
}
