#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e3 + 10;
int ans[MAXN * 3], vis[MAXN][MAXN];
int dp[MAXN][MAXN], n, kk, dir[4][2] = {1, 0, 0, 1};
char mp[MAXN][MAXN];
struct Node {
  int x, y, s;
  Node(int x, int y, int s) : x(x), y(y), s(s){};
};
queue<Node> q;
void bfs() {
  while (!q.empty()) {
    Node u = q.front();
    q.pop();
    int x = u.x;
    int y = u.y;
    int s = u.s;
    if (n == 100 && kk == 1 && q.size() > 100000) {
      printf("siz = %d, x = %d, y = %d, s = %d\n", q.size(), x, y, s);
      return;
    }
    if (s >= 2 * n - 1) continue;
    if (mp[x][y] - 'a' > ans[s]) continue;
    for (int i = 0; i < 2; i++) {
      int dx = x + dir[i][0];
      int dy = y + dir[i][1];
      if (dx > n || dy > n) continue;
      if (mp[dx][dy] - 'a' <= ans[s + 1] && vis[dx][dy] == 0) {
        vis[dx][dy] = 1;
        ans[s + 1] = mp[dx][dy] - 'a';
        q.push(Node(dx, dy, s + 1));
      }
    }
  }
}
int main() {
  cin >> n >> kk;
  memset(ans, INF, sizeof ans);
  memset(dp, -1, sizeof dp);
  for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
  int cnt = 0;
  if (kk) {
    if (mp[1][1] == 'a')
      dp[1][1] = kk;
    else
      dp[1][1] = kk - 1;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (i - 1 >= 1 && dp[i - 1][j] >= 0) {
          int tmp = dp[i - 1][j];
          if (mp[i][j] != 'a') tmp--;
          dp[i][j] = max(dp[i][j], tmp);
        }
        if (j - 1 >= 1 && dp[i][j - 1] >= 0) {
          int tmp = dp[i][j - 1];
          if (mp[i][j] != 'a') tmp--;
          dp[i][j] = max(dp[i][j], tmp);
        }
        if (dp[i][j] >= 0) cnt = max(cnt, i + j - 1);
      }
    if (dp[n][n] >= 0) {
      for (int i = 1; i < 2 * n; i++) printf("a");
      return 0;
    }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (dp[i][j] == 0 && i + j - 1 == cnt) {
          vis[i][j] = 1;
          q.push(Node(i, j, cnt));
          mp[i][j] = 'a';
        }
    for (int i = 1; i <= cnt; i++) ans[i] = 0;
  } else {
    vis[1][1] = 1;
    q.push(Node(1, 1, 1));
    ans[1] = mp[1][1] - 'a';
  }
  bfs();
  for (int i = 1; i < 2 * n; i++) printf("%c", ans[i] + 'a');
  return 0;
}
