#include <bits/stdc++.h>
using namespace std;
int dp[2005][2005];
bool used[2005][2005];
int n, k;
queue<pair<int, int> > q[2];
bool check(int x, int y) { return (0 <= x && x < n && 0 <= y && y < n); }
int main() {
  string ans = "";
  cin >> n >> k;
  vector<string> v(n);
  for (int i = 0; i < n; i++) cin >> v[i];
  for (int i = 0; i <= n; i++) {
    dp[0][i] = -123;
    dp[i][0] = -123;
  }
  if (k > 0) {
    dp[1][1] = k;
    if (v[0][0] != 'a') dp[1][1]--;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (i != 1 || j != 1)
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) - (v[i - 1][j - 1] != 'a');
    for (int i = 1; i < 2 * n; i++) ans += 'a';
    if (dp[n][n] >= 0) {
      cout << ans;
      return 0;
    }
    bool b = true;
    for (int i = n + n; i > 0; i--) {
      for (int j = n; j > 0 && i - j <= n; j--) {
        if (i - j <= 0) continue;
        if (dp[i - j][j] == 0) {
          b = false;
          v[i - j - 1][j - 1] = 'a';
          q[0].push(make_pair(i - j - 1, j - 1));
        }
      }
      if (!b) break;
      ans.pop_back();
    }
  } else {
    q[0].push(make_pair(0, 0));
    ans += v[0][0];
  }
  int id = 0;
  char best;
  pair<int, int> cur;
  for (;;) {
    best = 'z' + 1;
    while (!q[id].empty()) {
      cur = q[id].front();
      q[id].pop();
      if (used[cur.first][cur.second]) continue;
      if (cur.first == n - 1 && cur.second == n - 1) {
        cout << ans;
        return 0;
      }
      used[cur.first][cur.second] = true;
      if (check(cur.first + 1, cur.second)) {
        if (v[cur.first + 1][cur.second] < best) {
          while (!q[1 - id].empty()) q[1 - id].pop();
          best = v[cur.first + 1][cur.second];
        }
        if (v[cur.first + 1][cur.second] == best)
          q[1 - id].push(make_pair(cur.first + 1, cur.second));
      }
      if (check(cur.first, cur.second + 1)) {
        if (v[cur.first][cur.second + 1] < best) {
          while (!q[1 - id].empty()) q[1 - id].pop();
          best = v[cur.first][cur.second + 1];
        }
        if (v[cur.first][cur.second + 1] == best)
          q[1 - id].push(make_pair(cur.first, cur.second + 1));
      }
    }
    ans += best;
    id = 1 - id;
  }
  return 0;
}
