#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
const int M = 1e9 + 7;
const int INF = 2e9 + 5;
const int rx[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int ry[8] = {0, -1, 0, 1, 1, -1, 1, -1};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  char g[n][n];
  int dist[n][n];
  bool was[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> g[i][j];
      dist[i][j] = 1e9 + 7;
      was[i][j] = 0;
    }
  }
  dist[0][0] = 0;
  if (g[0][0] != 'a') dist[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int l = 0; l < 2; l++) {
        int a = i + rx[l];
        int b = j + ry[l];
        if (a >= 0 && b >= 0) {
          int cur = dist[a][b];
          if (g[i][j] != 'a') cur++;
          dist[i][j] = min(dist[i][j], cur);
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][j] <= k) g[i][j] = 'a';
    }
  }
  int cnt = 0;
  string ans = "";
  ans += g[0][0];
  queue<pair<int, pair<int, int>>> q1;
  q1.push({0, {0, 0}});
  while (!q1.empty()) {
    vector<pair<char, pair<int, int>>> can;
    while (q1.size() && q1.front().first == cnt) {
      int x = q1.front().second.first;
      int y = q1.front().second.second;
      q1.pop();
      for (int i = 0; i < 2; i++) {
        int a = x - rx[i];
        int b = y - ry[i];
        if (a < n && b < n && !was[a][b]) {
          can.push_back({g[a][b], {a, b}});
          was[a][b] = 1;
        }
      }
    }
    if (can.size()) {
      sort(can.begin(), can.end());
      ans += can[0].first;
      for (auto i : can) {
        if (i.first == can[0].first) {
          q1.push({cnt + 1, i.second});
        }
      }
      cnt++;
    }
  }
  cout << ans;
};
