#include <bits/stdc++.h>
using namespace std;
void Debug() { cout << '\n'; }
template <class FIRST, class... REST>
void Debug(FIRST arg, REST... rest) {
  cout << arg << " ";
  Debug(rest...);
}
template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  if (!v.empty()) {
    for (int i = int(0); i < int((int)(v).size() - 1); i++) out << v[i] << ", ";
    out << v.back();
  }
  out << "]";
  return out;
}
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& v) {
  out << "(" << v.first << ", " << v.second << ")";
  return out;
}
const int MAX_N = 300010;
const int MAX_V = 100010;
const double eps = 1e-6;
const long long mod = 1000000007;
const int inf = 1 << 30;
const long long linf = 1LL << 60;
const double PI = 3.14159265358979323846;
int N, K;
int dp[2010][2010];
string S[2010];
void solve() {
  cin >> N >> K;
  for (int i = int(0); i < int(N); i++) cin >> S[i];
  for (int i = int(0); i < int(N); i++) {
    for (int j = int(0); j < int(N); j++) {
      dp[i][j] = inf;
    }
  }
  dp[0][0] = (S[0][0] != 'a');
  for (int i = int(0); i < int(N); i++) {
    for (int j = int(0); j < int(N); j++) {
      if (i + 1 < N) {
        dp[i + 1][j] = min(dp[i + 1][j], (S[i + 1][j] != 'a') + dp[i][j]);
      }
      if (j + 1 < N) {
        dp[i][j + 1] = min(dp[i][j + 1], (S[i][j + 1] != 'a') + dp[i][j]);
      }
    }
  }
  int k = 0;
  while (true) {
    bool found = false;
    for (int i = 0; i <= k; i++) {
      if (0 <= i && i < N && 0 <= k - i && k - i < N) {
        if (dp[i][k - i] <= K) {
          found = true;
          break;
        }
      }
    }
    if (!found)
      break;
    else
      k++;
  }
  string str;
  for (int i = int(0); i < int(k); i++) str += 'a';
  set<pair<int, int> > vec;
  if (k == 0) {
    str += S[0][0];
    vec.insert(pair<int, int>(0, 0));
    k++;
  } else {
    for (int i = 0; i < k; i++) {
      if (0 <= i && i < N && 0 <= k - 1 - i && k - 1 - i < N) {
        if (dp[i][k - 1 - i] <= K) {
          vec.insert(pair<int, int>(i, k - 1 - i));
        }
      }
    }
  }
  for (int l = int(k); l < int(2 * N - 1); l++) {
    int a = inf;
    for (auto p : vec) {
      int x = p.first, y = p.second;
      if (x + 1 < N) a = min(a, S[x + 1][y] - 'a');
      if (y + 1 < N) a = min(a, S[x][y + 1] - 'a');
    }
    str += char(a + 'a');
    set<pair<int, int> > v;
    for (auto p : vec) {
      int x = p.first, y = p.second;
      if (x + 1 < N && S[x + 1][y] - 'a' == a)
        v.insert(pair<int, int>(x + 1, y));
      if (y + 1 < N && S[x][y + 1] - 'a' == a)
        v.insert(pair<int, int>(x, y + 1));
    }
    vec = v;
  }
  cout << str << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed;
  cout.precision(20);
  srand((unsigned int)time(NULL));
  solve();
  return 0;
}
