#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int ar[maxn][maxn];
int dp[maxn][maxn];
bool flag[maxn][maxn];
int n, k;
char ch;
struct node {
  int x, y;
} point;
queue<node> temp;
queue<node> q;
void bfs(int cha) {
  while (cha--) {
    int min_ch = 30;
    while (!temp.empty()) {
      point = temp.front();
      if (point.x == n - 1 && point.y == n - 1) break;
      if (point.x + 1 < n && !flag[point.x + 1][point.y]) {
        flag[point.x + 1][point.y] = 1;
        min_ch = min(min_ch, ar[point.x + 1][point.y]);
        point.x++;
        q.push(point);
        point.x--;
      }
      if (point.y + 1 < n && !flag[point.x][point.y + 1]) {
        flag[point.x][point.y + 1] = 1;
        min_ch = min(min_ch, ar[point.x][point.y + 1]);
        point.y++;
        q.push(point);
        point.y--;
      }
      temp.pop();
    }
    cout << (char)(min_ch + 'a');
    while (!q.empty()) {
      point = q.front();
      if (ar[point.x][point.y] == min_ch) temp.push(point);
      q.pop();
    }
  }
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> ch;
      ar[i][j] = ch - 'a';
    }
  }
  if (k) {
    int furthest = -1;
    dp[0][0] = 0;
    if (ar[0][0]) dp[0][0]++;
    if (dp[0][0] <= k) {
      point.x = 0, point.y = 0;
      q.push(point);
      furthest = 0;
    }
    for (int j = 1; j < n; j++) {
      dp[0][j] = dp[0][j - 1];
      if (ar[0][j]) dp[0][j]++;
      if (dp[0][j] <= k) {
        point.x = 0, point.y = j;
        q.push(point);
        furthest = j;
      }
    }
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (j) {
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
          if (ar[i][j]) dp[i][j]++;
        } else {
          dp[i][j] = dp[i - 1][j];
          if (ar[i][j]) dp[i][j]++;
        }
        if (dp[i][j] <= k) {
          point.x = i, point.y = j;
          q.push(point);
          furthest = max(furthest, i + j);
        }
      }
    }
    int cha = 2 * n - furthest - 2;
    int len = 2 * n - 1 - cha;
    for (int i = 1; i <= len; i++) printf("a");
    while (!q.empty()) {
      point = q.front();
      if (point.x + point.y == furthest) temp.push(point);
      q.pop();
    }
    bfs(cha);
  } else {
    point.x = 0, point.y = 0;
    temp.push(point);
    cout << (char)(ar[0][0] + 'a');
    bfs(2 * n - 2);
  }
  cout << endl;
  return 0;
}
