#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 4;
const int INF = 1e9 + 4;
struct cell {
  int i, j;
  char last;
  cell(int ii = 0, int jj = 0, char lastt = 'z') {
    i = ii;
    j = jj;
    last = lastt;
  }
};
int n, k, d = -1;
string tab[N];
void onlyA(int cnt) {
  for (int i = 0; i < cnt; ++i) {
    cout << "a";
  }
}
void read() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> tab[i];
  }
}
int dp[N][N];
pair<int, int> linkDp[N][N];
bool usDp[N][N];
int rec(int i, int j) {
  if (i < 0 || j < 0) {
    return -INF;
  }
  if (usDp[i][j]) {
    return dp[i][j];
  }
  usDp[i][j] = 1;
  return dp[i][j] = max(rec(i - 1, j), rec(i, j - 1)) + (tab[i][j] == 'a');
}
queue<cell> q;
bool usedTab[N][N];
string way;
void precalc() {
  usDp[0][0] = 1;
  dp[0][0] = (tab[0][0] == 'a');
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int acnt = rec(i, j);
      if (acnt + k >= 2 * n - 1) {
        onlyA(2 * n - 1);
        exit(0);
      }
      if (i + j + 1 - acnt - k == 0) {
        d = max(d, i + j);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i + j == d && i + j + 1 - rec(i, j) - k == 0) {
        q.push(cell(i, j, 'a'));
      }
    }
  }
  if (q.empty()) {
    way.push_back(tab[0][0]);
    q.push(cell(0, 0, tab[0][0]));
  }
}
void bfs() {
  int l = 1, r = q.size();
  while (q.size()) {
    int rt = r;
    char charMin = 'z';
    vector<cell> qtmp;
    for (int i = l; i <= rt; ++i) {
      cell top = q.front();
      q.pop();
      qtmp.push_back(top);
      int y = top.i;
      int x = top.j;
      if (x + 1 < n) {
        charMin = min(charMin, tab[y][x + 1]);
      }
      if (y + 1 < n) {
        charMin = min(charMin, tab[y + 1][x]);
      }
    }
    way.push_back(charMin);
    for (cell& elem : qtmp) {
      int x = elem.j;
      int y = elem.i;
      if (x + 1 < n && !usedTab[y][x + 1] && tab[y][x + 1] == charMin) {
        q.push(cell(y, x + 1, charMin));
        usedTab[y][x + 1] = 1;
        ++r;
      }
      if (y + 1 < n && !usedTab[y + 1][x] && tab[y + 1][x] == charMin) {
        q.push(cell(y + 1, x, charMin));
        usedTab[y + 1][x] = 1;
        ++r;
      }
    }
    l = rt + 1;
  }
  way.pop_back();
}
void write() {
  onlyA(d + 1);
  cout << way;
}
void solve() {
  read();
  precalc();
  bfs();
  write();
}
int main() {
  ios_base::sync_with_stdio(false);
  solve();
  return 0;
}
