#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, Mod = 1e9 + 7, MAXN = 1e5, Lg = 20, M = 1e7 + 10,
          P = 727, Sq = 320;
const long long inf = 3e18 + 10;
int n, c[N][N], k, dp[N][N], is[N][N];
pair<int, int> par[N][N];
vector<pair<int, int> > v, cur;
string ans = "";
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      char t;
      scanf(" %c", &t);
      c[i][j] = (t - 'a');
    }
  }
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    dp[1][i] = dp[1][i - 1];
    if (c[1][i] > 0) dp[1][i]++;
    dp[i][1] = dp[i - 1][1];
    if (c[i][1] > 0) dp[i][1]++;
    par[1][i] = make_pair(1, i - 1), par[i][1] = make_pair(i - 1, 1);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!dp[i][j]) {
        if (j > 1) dp[i][j] = dp[i][j - 1], par[i][j] = make_pair(i, j - 1);
        if (i > 1 && dp[i - 1][j] < dp[i][j - 1])
          dp[i][j] = dp[i - 1][j], par[i][j] = make_pair(i - 1, j);
        if (c[i][j] > 0) dp[i][j]++;
      }
      if (i + j > mx && dp[i][j] <= k) {
        mx = i + j;
        continue;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i + j == mx && dp[i][j] <= k) {
        v.push_back(make_pair(i, j));
      }
    }
  }
  if (v.size() && (v.back()).first == n && (v.back()).second == n) {
    for (int i = 0; i < 2 * n - 1; i++) cout << 'a';
    return 0;
  }
  if (!v.size()) {
    v.push_back(make_pair(1, 1));
  }
  while (1) {
    int mn = Mod;
    for (int i = 0; i < (int)v.size(); i++) {
      int a = v[i].first, b = v[i].second;
      if (a < n && c[a + 1][b] < mn) mn = c[a + 1][b];
      if (b < n && c[a][b + 1] < mn) mn = c[a][b + 1];
    }
    for (int i = 0; i < (int)v.size(); i++) {
      int a = v[i].first, b = v[i].second;
      if (a == n && b == n) {
        while (a && b) {
          ans += char(c[a][b] + 'a');
          int xs = par[a][b].first, xe = par[a][b].second;
          a = xs, b = xe;
        }
        reverse(ans.begin(), ans.end());
        for (int i = 0; i < (int)ans.size(); i++) {
          if (ans[i] != 'a' && k) {
            ans[i] = 'a';
            k--;
          }
          printf("%c", ans[i]);
        }
        return 0;
      }
      if (a < n && c[a + 1][b] == mn && !is[a + 1][b]) {
        cur.push_back(make_pair(a + 1, b));
        par[a + 1][b] = make_pair(a, b);
        is[a + 1][b] = 1;
      }
      if (b < n && c[a][b + 1] == mn && !is[a][b + 1]) {
        cur.push_back(make_pair(a, b + 1));
        par[a][b + 1] = make_pair(a, b);
        is[a][b + 1] = 1;
      }
    }
    v.clear();
    while (cur.size()) {
      v.push_back(cur.back());
      cur.pop_back();
    }
  }
}
