#include <bits/stdc++.h>
using namespace std;
struct elem {
  int i, j;
  char lastc;
  int k;
  elem() {
    lastc = 'z';
    k = -1;
  }
  elem(int i, int j, char lastc, int k) : i(i), j(j), lastc(lastc), k(k) {}
};
bool operator<(elem e1, elem e2) {
  if (e1.lastc != e2.lastc) return e1.lastc < e2.lastc;
  return e1.k > e2.k;
}
void minimize(elem &a, elem b) { a = min(a, b); }
void minimize(char &a, char b) { a = min(a, b); }
const int limit = 2005;
int n, k;
char t[limit][limit];
elem v[limit][limit];
int valid[limit][limit];
char sol[limit];
void add(elem e) {
  int i = e.i;
  int j = e.j;
  if (i < n - 1) minimize(v[i + 1][j], e);
  if (j < n - 1) minimize(v[i][j + 1], e);
}
bool inside(int i, int j) { return 0 <= i and i < n and 0 <= j and j < n; }
void move(int &i, int &j) {
  elem &e = v[i][j];
  i = e.i;
  j = e.j;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%s", t[i]);
  v[0][0].k = k;
  for (int ii = 0; ii < 2 * (n - 1); ii++) {
    char minc = 'z';
    for (int j = 0; j <= ii; j++) {
      int i = ii - j;
      if (not inside(i, j)) continue;
      elem &e = v[i][j];
      if (e.k >= 0) minimize(minc, e.lastc);
    }
    for (int j = 0; j <= ii; j++) {
      int i = ii - j;
      if (not inside(i, j)) continue;
      elem &e = v[i][j];
      valid[i][j] = e.k >= 0 and minc == e.lastc;
    }
    for (int j = 0; j <= ii; j++) {
      int i = ii - j;
      if (not inside(i, j)) continue;
      if (not valid[i][j]) continue;
      elem &e = v[i][j];
      if (t[i][j] == 'a')
        add(elem(i, j, 'a', e.k));
      else if (e.k > 0)
        add(elem(i, j, 'a', e.k - 1));
      else
        add(elem(i, j, t[i][j], e.k));
    }
  }
  int nsol = 0;
  {
    int i = n - 1, j = n - 1;
    if (v[i][j].k > 0)
      sol[nsol++] = 'a';
    else
      sol[nsol++] = t[i][j];
    while (not(i == 0 and j == 0)) {
      sol[nsol++] = v[i][j].lastc;
      move(i, j);
    }
  }
  sol[nsol] = 0;
  for (int i = 0, j = nsol - 1; i < j; i++, j--) swap(sol[i], sol[j]);
  printf("%s\n", sol);
}
