#include <bits/stdc++.h>
using namespace std;
const int N = 2010, A = 25;
int n, k;
pair<bool, int> opt[N][N];
string s[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  opt[0][0].first = 1;
  opt[0][0].second = k;
  if (s[0][0] != 'a' && opt[0][0].second > 0) {
    cout << 'a';
    opt[0][0].second--;
  } else
    cout << s[0][0];
  for (int i = 1; i < 2 * n - 1; ++i) {
    char maxi = 'z';
    char change = 'z';
    for (int x = max(0, i - n + 1); x <= min(i, n - 1); ++x) {
      int y = i - x;
      if ((y != 0 && opt[y - 1][x].first == 1) ||
          (x != 0 && opt[y][x - 1].first == 1)) {
        int v1 = 0;
        if (y != 0 && opt[y - 1][x].first == 1) v1 = opt[y - 1][x].second;
        int v2 = 0;
        if (x != 0 && opt[y][x - 1].first == 1) v2 = opt[y][x - 1].second;
        int maxk = max(v1, v2);
        if (s[y][x] != 'a' && maxk > 0) {
          s[y][x] = 'a';
          maxk--;
        }
        opt[y][x].second = maxk;
        maxi = min(maxi, s[y][x]);
      }
    }
    cout << maxi;
    for (int x = max(0, i - n + 1); x <= min(i, n - 1); ++x) {
      int y = i - x;
      if ((y != 0 && opt[y - 1][x].first == 1) ||
          (x != 0 && opt[y][x - 1].first == 1)) {
        if (s[y][x] <= maxi) {
          opt[y][x].first = 1;
        }
      }
    }
  }
}
