#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
char mp[MAXN][MAXN];
int f[MAXN][MAXN], vis[MAXN][MAXN];
int n, k;
struct P {
  int x, y;
  bool operator<(const P& rhs) const {
    if (x != rhs.x) return x < rhs.x;
    return y < rhs.y;
  }
};
vector<P> vec[MAXN + MAXN];
deque<P> Q;
set<pair<char, P> > S1, S2;
void add(int x, int y, int fromX, int fromY) {
  if (mp[x][y] == 'a') {
    Q.push_front(P{x, y});
    vis[x][y] = vis[fromX][fromY];
  } else {
    Q.push_back(P{x, y});
    vis[x][y] = vis[fromX][fromY] + 1;
  }
}
void allA() {
  for (int i = 1; i <= 2 * n - 1; i++) {
    putchar('a');
  }
  puts("");
  exit(0);
}
void add2(int x, int y) { S2.insert({mp[x][y], {x, y}}); }
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%s", mp[i] + 1);
  }
  memset(vis, -1, sizeof(vis));
  Q.push_back(P{1, 1});
  if (mp[1][1] != 'a') {
    vis[1][1] = 1;
  } else {
    vis[1][1] = 0;
  }
  while (!Q.empty()) {
    P cur = Q.front();
    Q.pop_front();
    int x = cur.x, y = cur.y, v = vis[x][y];
    vec[v].push_back(P{x, y});
    if (v <= k) {
      if (x < n && vis[x + 1][y] == -1) {
        add(x + 1, y, x, y);
      }
      if (y < n && vis[x][y + 1] == -1) {
        add(x, y + 1, x, y);
      }
    }
  }
  if (vis[n][n] != -1 && vis[n][n] <= k) allA();
  int ans = 0;
  for (auto t : vec[k + 1]) ans = max(ans, t.x + t.y - 2);
  for (int i = 1; i <= ans; i++) {
    putchar('a');
  }
  for (auto t : vec[k + 1]) {
    if (t.x + t.y - 2 == ans) {
      S1.insert(make_pair(mp[t.x][t.y], P{t.x, t.y}));
    }
  }
  for (int i = ans + 1; i <= 2 * n - 1; i++) {
    putchar((*S1.begin()).first);
    S2.clear();
    for (auto p : S1) {
      if (p.first != (*S1.begin()).first) continue;
      if (p.second.x < n) add2(p.second.x + 1, p.second.y);
      if (p.second.y < n) add2(p.second.x, p.second.y + 1);
    }
    swap(S1, S2);
  }
  puts("");
  return 0;
}
