#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 229;
const int M = 1e9 + 7;
const int mod = 998244353;
const int rx[4] = {1, -1, -1, 1};
const int ry[4] = {1, -1, 1, -1};
const double eps = 0.000001;
const double pi = acos(-1);
int dp[2100][2100];
char a[2100][2100];
int best;
char calc[4100];
bool used[2100][2100];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  srand(time(0));
  for (int i = 0; i < 4100; ++i) {
    calc[i] = char(int('z') + 1);
  }
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (a[i][j] == 'a') {
        dp[i][j] = 1;
      }
      if (i && j) {
        dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);
      } else if (i) {
        dp[i][j] += dp[i - 1][j];
      } else if (j) {
        dp[i][j] += dp[i][j - 1];
      }
    }
  }
  char now = 'z';
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i + j + 1 - dp[i][j] - k <= 0 && i + j + 1 > best) {
        best = i + j + 1;
      }
    }
  }
  now = 'a';
  queue<pair<char, pair<int, int> > > q;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i + j + 1 - dp[i][j] - k <= 0 && i + j + 1 == best) {
        calc[i + j + 1] = now;
        q.push({'a', {i, j}});
        used[i][j] = 1;
      }
    }
  }
  if (!best) {
    now = a[0][0];
    calc[1] = a[0][0];
    q.push({a[0][0], {0, 0}});
    used[0][0] = 1;
  }
  char x;
  while (!q.empty()) {
    int i = q.front().second.first, j = q.front().second.second;
    char x = q.front().first;
    q.pop();
    if (x != calc[i + j + 1]) {
      continue;
    }
    now = calc[i + j + 1];
    if (i + 1 < n && !used[i + 1][j] && a[i + 1][j] <= calc[i + j + 2]) {
      if (calc[i + j + 2] > a[i + 1][j]) {
        calc[i + j + 2] = a[i + 1][j];
      }
      q.push({a[i + 1][j], {i + 1, j}});
      used[i + 1][j] = 1;
    }
    if (j + 1 < n && !used[i][j + 1] && a[i][j + 1] <= calc[i + j + 2]) {
      if (calc[i + j + 2] > a[i][j + 1]) {
        calc[i + j + 2] = a[i][j + 1];
      }
      q.push({a[i][j + 1], {i, j + 1}});
      used[i][j + 1] = 1;
    }
  }
  for (int i = 0; i < best; ++i) {
    cout << 'a';
  }
  for (int i = best + 1; i < n + n; ++i) {
    cout << calc[i];
  }
  return 0;
}
