#include <bits/stdc++.h>
namespace chtholly {
char buf[1 << 23], *p1 = buf, *p2 = buf;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f ^= c == '-';
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return f ? x : -x;
}
template <typename mitsuha>
inline bool read(mitsuha &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  for (; !isdigit(c) && ~c; c = getchar()) f ^= c == '-';
  if (!~c) return 0;
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ '0');
  return x = f ? x : -x, 1;
}
template <typename mitsuha>
inline int write(mitsuha x) {
  if (!x) return 0 & putchar(48);
  if (x < 0) putchar('-'), x = -x;
  int bit[20], i, p = 0;
  for (; x; x /= 10) bit[++p] = x % 10;
  for (i = p; i; --i) putchar(bit[i] + 48);
  return 0;
}
inline char fuhao() {
  char c = getchar();
  for (; isspace(c); c = getchar())
    ;
  return c;
}
}  // namespace chtholly
using namespace chtholly;
using namespace std;
const int aoi = 2018;
char c[aoi][aoi];
string llx;
int n, k, da[aoi][aoi], xiao = 9999999, in[aoi][aoi];
vector<pair<int, int> > now, tmp;
struct node {
  string s;
  int x, y, k;
  bool operator<(const node &b) const { return s > b.s; }
};
string bfs(int sx, int sy) {
  priority_queue<node> q;
  string s;
  if (c[sx][sy] ^ 'a' && k > 0)
    --k, s = string(1, 'a');
  else
    s = string(1, c[sx][sy]);
  q.push(node{s, sx, sy, k});
  for (; !q.empty();) {
    node u = q.top();
    q.pop();
    cout << u.x << " " << u.y << " " << u.s << endl;
    if (u.x == n && u.y == n) return u.s;
    if (u.y < n) {
      int nx = u.x, ny = u.y + 1;
      string net;
      if (c[nx][ny] == 'a' || u.k > 0) {
        net = u.s + 'a';
        if (c[nx][ny] ^ 'a') --u.k;
      } else {
        net = u.s + c[nx][ny];
      }
      q.push(node{net, nx, ny, u.k});
    }
    if (u.x < n) {
      int nx = u.x + 1, ny = u.y;
      string net;
      if (c[nx][ny] == 'a' || u.k > 0) {
        net = u.s + 'a';
        if (c[nx][ny] ^ 'a') --u.k;
      } else {
        net = u.s + c[nx][ny];
      }
      q.push(node{net, nx, ny, u.k});
    }
  }
}
int main() {
  int i, j;
  read(n), read(k);
  for (i = 1; i <= n; ++i) scanf("%s", c[i] + 1);
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      da[i][j] = max(da[i - 1][j], da[i][j - 1]) + (c[i][j] == 'a');
      xiao = min(xiao, i + j - 1 - da[i][j]);
    }
  }
  if (n * 2 - 1 - da[n][n] <= k) {
    for (i = 1; i <= n * 2 - 1; ++i) printf("a");
    return 0;
  }
  int t = 0;
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= n; ++j)
      if (i + j - 1 - da[i][j] <= k) t = max(t, i + j);
  for (i = 1; i < t; ++i) llx += "a";
  for (i = 1; i <= n; ++i)
    for (j = 1; j <= n; ++j)
      if (i + j - 1 - da[i][j] <= k && i + j == t)
        now.push_back(pair<int, int>(i, j));
  if (!k) llx = c[1][1], now.push_back(pair<int, int>(1, 1));
  for (; now.front() != pair<int, int>(n, n);) {
    char u = '{';
    for (i = 0; i < now.size(); ++i) {
      pair<int, int> t2 = now[i];
      int p = t2.first, q = t2.second;
      if (p + 1 <= n) u = min(u, c[p + 1][q]);
      if (q + 1 <= n) u = min(u, c[p][q + 1]);
    }
    llx += u;
    for (i = 0; i < now.size(); ++i) {
      pair<int, int> t2 = now[i];
      int p = t2.first, q = t2.second;
      if (p + 1 <= n && c[p + 1][q] == u && !in[p + 1][q])
        tmp.push_back(pair<int, int>(p + 1, q)), in[p + 1][q] = 1;
      if (q + 1 <= n && c[p][q + 1] == u && !in[p][q + 1])
        tmp.push_back(pair<int, int>(p, q + 1)), in[p][q + 1] = 1;
    }
    now.clear();
    for (i = 0; i < tmp.size(); ++i) now.push_back(tmp[i]);
    tmp.clear();
  }
  cout << llx << endl;
}
