#include <bits/stdc++.h>
using namespace std;
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
struct P {
  int x, y;
  char c;
  P() {}
  P(int x, int y, char c) : x(x), y(y), c(c) {}
  bool operator<(const P& a) const { return c < a.c; }
};
int n, m;
string S[2010];
bool ok[2010][2010];
int rem[2010][2010];
int dx[2] = {0, 1};
int dy[2] = {1, 0};
string ans;
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) cin >> S[i];
  ok[0][0] = true;
  rem[0][0] = m;
  for (int i = 0; i < 2 * n - 1; i++) {
    int s = 0;
    if (i >= n) s = i - n + 1;
    int t = i;
    if (i >= n) t = n - 1;
    vector<P> vec;
    for (int j = s; j <= t; j++) {
      int x = j, y = i - j;
      if (ok[x][y]) vec.push_back(P(x, y, (rem[x][y] > 0) ? 'a' : S[x][y]));
    }
    sort((vec).begin(), (vec).end());
    ans += vec[0].c;
    for (int j = 0; j < vec.size(); j++) {
      if (vec[j].c != vec[0].c) break;
      int x = vec[j].x;
      int y = vec[j].y;
      for (int d = 0; d < 2; d++) {
        int nx = vec[j].x + dx[d];
        int ny = vec[j].y + dy[d];
        if (nx >= n || ny >= n) continue;
        ok[nx][ny] = true;
        if (vec[j].c != S[x][y])
          rem[nx][ny] = max(rem[nx][ny], rem[x][y] - 1);
        else
          rem[nx][ny] = max(rem[nx][ny], rem[x][y]);
      }
    }
  }
  cout << ans << endl;
  return 0;
}
