#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  int f = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = 1;
    if (ch == EOF) return;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  if (f) x = -x;
}
const int MAXN = 2011;
char s[MAXN][MAXN];
int dp[MAXN][MAXN];
int n, k;
queue<pair<int, int> > Q;
pair<int, int> tmp[MAXN * MAXN];
int vis[MAXN][MAXN];
string ans = "";
inline void Work() {
  int cnt = 0;
  while (!Q.empty()) {
    pair<int, int> now = Q.front();
    Q.pop();
    if (now.first + 1 <= n) tmp[++cnt] = make_pair(now.first + 1, now.second);
    if (now.second + 1 <= n) tmp[++cnt] = make_pair(now.first, now.second + 1);
  }
  char res = 'z';
  for (int i = 1; i <= cnt; ++i) {
    res = min(res, s[tmp[i].first][tmp[i].second]);
    vis[tmp[i].first][tmp[i].second] = 0;
  }
  ans += res;
  for (int i = 1; i <= cnt; ++i) {
    if (s[tmp[i].first][tmp[i].second] == res &&
        !vis[tmp[i].first][tmp[i].second]) {
      vis[tmp[i].first][tmp[i].second] = 1;
      Q.push(tmp[i]);
    }
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s[i] + 1);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dp[i][j] = (s[i][j] == 'a' ? 0 : 1);
      if (i == 1 && j == 1) continue;
      dp[i][j] +=
          min((i > 1 ? dp[i - 1][j] : 1e9), (j > 1 ? dp[i][j - 1] : 1e9));
    }
  }
  int mn = n - 2 + n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dp[i][j] <= k) {
        mn = min(mn, (n - i) + (n - j));
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dp[i][j] <= k && (n - i) + (n - j) == mn) {
        Q.push(make_pair(i, j));
      }
    }
  }
  if (Q.empty()) {
    mn = n - 2 + n;
    Q.push(make_pair(1, 1));
    ans += s[1][1];
  } else {
    for (int i = n - 2 + n; i >= mn; --i) {
      ans += 'a';
    }
  }
  for (int i = 1; i <= mn; ++i) {
    Work();
  }
  cout << ans << endl;
  return 0;
}
