#include <bits/stdc++.h>
using namespace std;
int n, k;
char m[2005][2005];
int mk[2005][2005];
int p[2005][2005];
struct node {
  int x, y;
};
int getid(int x, int y) { return (x - 1) * (n + 1) + y; }
vector<int> vec, que;
unordered_set<int> s;
string ans = "";
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    getchar();
    for (int j = 1; j <= n; j++) {
      scanf("%c", &m[i][j]);
      p[i][j] = mk[i][j] = -1;
    }
  }
  if (k >= 2 * n - 1) {
    for (int i = 1; i <= 2 * n - 1; i++) printf("a");
    printf("\n");
    return 0;
  }
  int maxx = 0;
  mk[1][1] = k - (m[1][1] == 'a' ? 0 : 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == 1 && j != 1)
        mk[1][j] = mk[1][j - 1] - (m[1][j] == 'a' ? 0 : 1);
      else if (j == 1 && i != 1)
        mk[i][1] = mk[i - 1][1] - (m[i][1] == 'a' ? 0 : 1);
      else if (i != 1 && j != 1)
        mk[i][j] = max(mk[i - 1][j], mk[i][j - 1]) - (m[i][j] == 'a' ? 0 : 1);
      if (!mk[i][j]) {
        if (i + j - 1 > maxx) {
          maxx = i + j - 1;
          vec.clear();
          vec.push_back(getid(i, j));
        } else if (i + j - 1 == maxx)
          vec.push_back(getid(i, j));
      }
    }
  }
  if (mk[n][n] >= 0) {
    for (int i = 1; i <= 2 * n - 1; i++) printf("a");
    printf("\n");
    return 0;
  }
  for (int i = 0; i < vec.size(); i++)
    p[vec[i] / (n + 1) + 1][vec[i] % (n + 1)] = 0;
  int turn = 0;
  if (k == 0 && m[1][1] != 'a') {
    p[1][1] = 1;
    vec.push_back(getid(1, 1));
    turn = 1;
    ans += m[1][1];
  }
  while (p[n][n] == -1) {
    turn++;
    char minc = 'z' + 1;
    for (int i = 0; i < vec.size(); i++) {
      int px = vec[i] / (n + 1) + 1, py = vec[i] % (n + 1);
      if (px + 1 <= n && m[px + 1][py] < minc) {
        minc = m[px + 1][py];
        que.clear();
        que.push_back(getid(px + 1, py));
      } else if (px + 1 <= n && m[px + 1][py] == minc)
        que.push_back(getid(px + 1, py));
      if (py + 1 <= n && m[px][py + 1] < minc) {
        minc = m[px][py + 1];
        que.clear();
        que.push_back(getid(px, py + 1));
      } else if (py + 1 <= n && m[px][py + 1] == minc)
        que.push_back(getid(px, py + 1));
    }
    ans += minc;
    vec.clear();
    s.clear();
    for (int i = 0; i < que.size(); i++) {
      p[que[i] / (n + 1) + 1][que[i] % (n + 1)] = turn;
      if (s.find(que[i]) == s.end()) {
        s.insert(que[i]);
        vec.push_back(que[i]);
      }
    }
    que.clear();
  }
  for (int i = 1; i <= maxx; i++) printf("a");
  cout << ans << endl;
  return 0;
}
