#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
struct Node {
  int x, y;
  Node(int _x, int _y) {
    x = _x;
    y = _y;
  }
};
char s[N][N];
char ans[N << 1];
int cnt[N][N], visited[N][N];
priority_queue<Node> pq;
bool operator<(Node p, Node q) {
  if (p.x + p.y == q.x + q.y) return s[p.x][p.y] > s[q.x][q.y];
  return p.x + p.y > q.x + q.y;
}
int main() {
  int n, k, rec, x, y, minx, flag;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%s", s[i]);
  if (s[0][0] == 'a')
    cnt[0][0] = 0;
  else
    cnt[0][0] = 1;
  for (int i = 1; i < n; i++)
    cnt[0][i] = cnt[0][i - 1] + (s[0][i] == 'a' ? 0 : 1);
  for (int i = 1; i < n; i++) {
    cnt[i][0] = cnt[i - 1][0] + (s[i][0] == 'a' ? 0 : 1);
    for (int j = 1; j < n; j++)
      cnt[i][j] = min(cnt[i - 1][j], cnt[i][j - 1]) + (s[i][j] == 'a' ? 0 : 1);
  }
  if (cnt[n - 1][n - 1] <= k) {
    for (int i = 0; i <= n * 2 - 2; i++) printf("a");
    printf("\n");
    return 0;
  }
  flag = 1;
  rec = -1;
  for (int i = n * 2 - 2; i >= 0; i--) {
    for (int j = max(0, i - n + 1); j < min(n, i + 1); j++) {
      if (cnt[j][i - j] <= k) {
        rec = i;
        flag = 0;
        break;
      }
    }
    if (!flag) break;
  }
  for (int i = rec + 1; i <= n * 2 - 2; i++) ans[i] = 'z';
  memset(visited, 0, sizeof(visited));
  if (rec == -1) {
    pq.push(Node(0, 0));
    visited[0][0] = 1;
  } else {
    for (int i = max(0, rec - n + 1); i < min(n, rec + 1); i++) {
      if (cnt[i][rec - i] == k) {
        if (i < n - 1 && !visited[i + 1][rec - i]) {
          pq.push(Node(i + 1, rec - i));
          visited[i + 1][rec - i] = 1;
        }
        if (rec - i < n - 1 && !visited[i][rec - i + 1]) {
          pq.push(Node(i, rec - i + 1));
          visited[i][rec - i + 1] = 1;
        }
      }
    }
  }
  while (!pq.empty()) {
    x = pq.top().x;
    y = pq.top().y;
    pq.pop();
    if (s[x][y] > ans[x + y]) continue;
    if (ans[x + y] > s[x][y]) ans[x + y] = s[x][y];
    if (x < n - 1 && !visited[x + 1][y]) {
      pq.push(Node(x + 1, y));
      visited[x + 1][y] = 1;
    }
    if (y < n - 1 && !visited[x][y + 1]) {
      pq.push(Node(x, y + 1));
      visited[x][y + 1] = 1;
    }
  }
  for (int i = 0; i <= rec; i++) printf("a");
  for (int i = rec + 1; i <= n * 2 - 2; i++) printf("%c", ans[i]);
  printf("\n");
  return 0;
}
