#include <bits/stdc++.h>
using namespace std;
int n, k;
char a[2001][2001];
bool v[2001][2001];
int K[2001][2001];
char L[2001][2001];
char ans[4010];
struct record {
  int i, j, depth;
};
queue<record> Q;
int main() {
  scanf("%d%d", &n, &k);
  memset(L, 'z', sizeof L);
  for (int i = 0; i < n; i++) scanf("%s", a[i]);
  Q.emplace((record){0, 0, 0});
  K[0][0] = k;
  while (!Q.empty()) {
    auto x = Q.front();
    Q.pop();
    if (x.depth > 0 && L[x.i][x.j] != ans[x.depth - 1]) continue;
    if (a[x.i][x.j] == 'a') {
      ans[x.depth] = 'a';
      if (x.i + 1 < n &&
          (!v[x.i + 1][x.j] || ans[x.depth] <= L[x.i + 1][x.j])) {
        L[x.i + 1][x.j] = ans[x.depth];
        K[x.i + 1][x.j] = max(K[x.i][x.j], K[x.i + 1][x.j]);
        if (!v[x.i + 1][x.j]) Q.emplace((record){x.i + 1, x.j, x.depth + 1});
        v[x.i + 1][x.j] = 1;
      }
      if (x.j + 1 < n &&
          (!v[x.i][x.j + 1] || ans[x.depth] <= L[x.i][x.j + 1])) {
        L[x.i][x.j + 1] = ans[x.depth];
        K[x.i][x.j + 1] = max(K[x.i][x.j], K[x.i][x.j + 1]);
        if (!v[x.i][x.j + 1]) Q.emplace((record){x.i, x.j + 1, x.depth + 1});
        v[x.i][x.j + 1] = 1;
      }
    } else if (K[x.i][x.j] > 0) {
      ans[x.depth] = 'a';
      if (x.i + 1 < n &&
          (!v[x.i + 1][x.j] || ans[x.depth] <= L[x.i + 1][x.j])) {
        L[x.i + 1][x.j] = ans[x.depth];
        K[x.i + 1][x.j] = max(K[x.i][x.j] - 1, K[x.i + 1][x.j]);
        if (!v[x.i + 1][x.j]) Q.emplace((record){x.i + 1, x.j, x.depth + 1});
        v[x.i + 1][x.j] = 1;
      }
      if (x.j + 1 < n &&
          (!v[x.i][x.j + 1] || ans[x.depth] <= L[x.i][x.j + 1])) {
        L[x.i][x.j + 1] = ans[x.depth];
        K[x.i][x.j + 1] = max(K[x.i][x.j] - 1, K[x.i][x.j + 1]);
        if (!v[x.i][x.j + 1]) Q.emplace((record){x.i, x.j + 1, x.depth + 1});
        v[x.i][x.j + 1] = 1;
      }
    } else if (a[x.i][x.j] <= ans[x.depth] || ans[x.depth] == '\0') {
      ans[x.depth] = a[x.i][x.j];
      if (x.i + 1 < n &&
          (!v[x.i + 1][x.j] || ans[x.depth] <= L[x.i + 1][x.j])) {
        L[x.i + 1][x.j] = ans[x.depth];
        K[x.i + 1][x.j] = max(K[x.i][x.j], K[x.i + 1][x.j]);
        if (!v[x.i + 1][x.j]) Q.emplace((record){x.i + 1, x.j, x.depth + 1});
        v[x.i + 1][x.j] = 1;
      }
      if (x.j + 1 < n &&
          (!v[x.i][x.j + 1] || ans[x.depth] <= L[x.i][x.j + 1])) {
        L[x.i][x.j + 1] = ans[x.depth];
        K[x.i][x.j + 1] = max(K[x.i][x.j], K[x.i][x.j + 1]);
        if (!v[x.i][x.j + 1]) Q.emplace((record){x.i, x.j + 1, x.depth + 1});
        v[x.i][x.j + 1] = 1;
      }
    }
  }
  printf("%s", ans);
}
