#include <bits/stdc++.h>
using namespace std;
const int LOG = 18;
const int NN = 2222;
const int MOD = (int)1e9 + 7;
const int INF = 1LL << 28;
int mul(int x, int y) { return (1LL * x * y) % MOD; }
int add(int x, int y) { return (0LL + x + y) % MOD; }
int fast_pow(int x, int y) {
  if (y == 0) return 1;
  if (y & 1)
    return mul(x, fast_pow(x, y - 1));
  else {
    int aux = fast_pow(x, y >> 1);
    return mul(aux, aux);
  }
}
int n, k;
int ans;
char s[NN][NN];
int q[NN * NN * 2];
int timer[30];
bool vis[NN][NN];
int dp[NN][NN];
int rec(int x, int y) {
  if (x == -1 || y == -1) return 0;
  int& res = dp[x][y];
  if (~res) return res;
  res = 0;
  res = ((res) > (rec(x - 1, y) + (s[x][y] == 'a'))
             ? (res)
             : (rec(x - 1, y) + (s[x][y] == 'a')));
  res = ((res) > (rec(x, y - 1) + (s[x][y] == 'a'))
             ? (res)
             : (rec(x, y - 1) + (s[x][y] == 'a')));
  return res;
}
void bfs() {
  memset(dp, -1, sizeof(dp));
  int mx_k = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int d = i + j + 1;
      if (k + rec(i, j) >= d && d > mx_k) {
        mx_k = d;
      }
    }
  }
  int sz = 0;
  int cur_time = 1;
  memset(vis, false, sizeof(vis));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int d = i + j + 1;
      if (d == mx_k + 1 &&
          (k + rec(i - 1, j) >= d - 1 || k + rec(i, j - 1) >= d - 1)) {
        q[sz++] = i;
        q[sz++] = j;
        timer[s[i][j] - 'a'] = cur_time;
        vis[i][j] = true;
      }
    }
  }
  string ans;
  for (int i = 0; i < sz;) {
    char best = '?';
    for (int j = 0; j < 30; j++)
      if (timer[j] == cur_time) {
        best = (char)(j + 'a');
        break;
      }
    cur_time++;
    ans += best;
    int pre_sz = sz;
    while (i < pre_sz) {
      int x = q[i++], y = q[i++];
      if (s[x][y] != best) continue;
      for (int k = 0; k < 2; k++) {
        int nx = x + (k == 0);
        int ny = y + (k == 1);
        if (nx < n && ny < n && vis[nx][ny] == false) {
          vis[nx][ny] = true;
          q[sz++] = nx;
          q[sz++] = ny;
          timer[s[nx][ny] - 'a'] = cur_time;
        }
      }
    }
  }
  printf("%s%s\n", string(mx_k, 'a').c_str(), ans.c_str());
  return;
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%s", s[i]);
  bfs();
  return 0;
}
