#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const long long INF = 4 * (long long)1e18 + 7;
const double eps = 1e-9;
struct Point {
  int x;
  int y;
};
signed main() {
  ios_base::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  vector<vector<char>> field(n + 2, vector<char>(n + 2, 'z' + 1));
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= n; i++) {
      cin >> field[j][i];
    }
  }
  vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= n; i++) {
      dp[j][i] = max(dp[j - 1][i], dp[j][i - 1]);
      if (field[j][i] == 'a') dp[j][i]++;
    }
  }
  vector<vector<bool>> used(n + 2, vector<bool>(n + 2, false));
  vector<Point> edge;
  vector<Point> newedge;
  int maxv = -1;
  for (int j = 1; j <= n; j++) {
    for (int i = 1; i <= n; i++) {
      if (k + dp[j][i] >= i + j - 1) {
        if (dp[j][i] == maxv) {
          edge.push_back({i, j});
          used[j][i] = true;
        } else if (dp[j][i] > maxv) {
          edge.clear();
          edge.push_back({i, j});
          maxv = dp[j][i];
          used[j][i] = true;
        }
      }
    }
  }
  string s;
  for (int i = 0; i < min(2 * n - 1, maxv + k); i++) {
    s += 'a';
  }
  if (edge.empty()) {
    edge.push_back({1, 1});
    s += field[1][1];
  }
  while (1) {
    char minch = 'z' + 1;
    for (Point p : edge) {
      Point a = {p.x, p.y + 1};
      Point b = {p.x + 1, p.y};
      if (!used[a.y][a.x]) minch = min(minch, field[a.y][a.x]);
      if (!used[b.y][b.x]) minch = min(minch, field[b.y][b.x]);
    }
    if (minch == 'z' + 1) break;
    for (Point p : edge) {
      Point a = {p.x, p.y + 1};
      Point b = {p.x + 1, p.y};
      if (field[a.y][a.x] == minch && !used[a.y][a.x]) {
        newedge.push_back({a.x, a.y});
        used[a.y][a.x] = true;
      }
      if (field[b.y][b.x] == minch && !used[b.y][b.x]) {
        newedge.push_back({b.x, b.y});
        used[b.y][b.x] = true;
      }
    }
    s += minch;
    edge = newedge;
    newedge.clear();
  }
  cout << s << endl;
  return 0;
}
