#include <bits/stdc++.h>
const int N = 200001;
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k;
  cin >> n >> k;
  char a[n + 5][n + 5];
  memset(a, '|', sizeof a);
  int dp[n + 5][n + 5];
  for (int i = 1; i < n + 1; i++) {
    for (int j = 1; j < n + 1; j++) {
      cin >> a[i][j];
    }
  }
  if (n == 1) {
    cout << (k || a[1][1] == 'a' ? 'a' : a[1][1]);
    return 0;
  }
  string ans;
  vector<pair<int, int>> b;
  bool vis[n + 5][n + 5];
  memset(vis, false, sizeof vis);
  if (k) {
    dp[1][1] = (a[1][1] > 'a');
    for (int i = 2; i < n + 1; i++) {
      dp[i][1] = (a[i][1] > 'a') + dp[i - 1][1];
    }
    for (int j = 2; j < n + 1; j++) {
      dp[1][j] = (a[1][j] > 'a') + dp[1][j - 1];
    }
    int maxi = 0;
    for (int i = 2; i < n + 1; i++) {
      for (int j = 2; j < n + 1; j++) {
        dp[i][j] = (a[i][j] > 'a') + min(dp[i - 1][j], dp[i][j - 1]);
      }
    }
    for (int i = 1; i < n + 1; i++) {
      for (int j = 1; j < n + 1; j++) {
        if (dp[i][j] <= k) {
          maxi = max(maxi, i + j);
        }
      }
    }
    ans = string(maxi - 1, 'a');
    for (int i = 1; i < min(n + 1, maxi); i++) {
      if (maxi - i < n + 1 && dp[i][maxi - i] <= k) {
        b.push_back(make_pair(i, maxi - i));
        vis[i][maxi - i] = true;
      }
    }
  } else {
    ans += a[1][1];
    b.push_back(make_pair(1, 1));
  }
  while (ans.size() < 2 * n - 1) {
    vector<pair<int, int>> nex;
    char c = '|';
    for (auto e : b) {
      int x = e.first, y = e.second;
      if (!vis[x + 1][y]) {
        c = min(c, a[x + 1][y]);
      }
      if (!vis[x][y + 1]) {
        c = min(c, a[x][y + 1]);
      }
    }
    ans += c;
    for (auto e : b) {
      int x = e.first, y = e.second;
      if (!vis[x + 1][y] && a[x + 1][y] == c) {
        nex.push_back(make_pair(x + 1, y));
        vis[x + 1][y] = true;
      }
      if (!vis[x][y + 1] && a[x][y + 1] == c) {
        nex.push_back(make_pair(x, y + 1));
        vis[x][y + 1] = true;
      }
    }
    b = nex;
  }
  cout << ans;
}
