#include <bits/stdc++.h>
using namespace std;
void read(int &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
  return;
}
char c[2005][2005];
int lt[2005][2005];
bool used[2005][2005];
int n;
int now = 1;
int maxx = 0;
int getlastlt(int i, int j) {
  if (!i) return lt[i][j - 1];
  if (!j) return lt[i - 1][j];
  return (((lt[i][j - 1]) > (lt[i - 1][j])) ? (lt[i][j - 1]) : (lt[i - 1][j]));
}
string MINn(string x, string y) {
  int la = x.size(), lb = y.size();
  int p = 0;
  while (p < la && p < lb) {
    if (x[p] < y[p]) return x;
    if (x[p] > y[p]) return y;
    p++;
  }
  return x;
}
int main() {
  memset(lt, 0, sizeof(lt));
  memset(used, 0, sizeof(used));
  cin >> n >> lt[0][0];
  for (int i = 0; i < n; ++i) scanf("%s", c[i]);
  if (c[0][0] != 'a' && lt[0][0]) --lt[0][0], c[0][0] = 'a';
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i || j) {
        int tmp = getlastlt(i, j);
        if (c[i][j] == 'a') tmp++, maxx = i + j;
        if (tmp) lt[i][j] = --tmp, c[i][j] = 'a';
      }
    }
  }
  string ans;
  ans.push_back(c[0][0]);
  used[0][0] = 1;
  for (int i = 1; i <= 2 * n - 2; ++i) {
    int rr, cc;
    char minn = 'z' + 1;
    if (i <= n - 1) {
      rr = i;
      cc = 0;
      while (rr >= 0) {
        if ((rr && used[rr - 1][cc]) || (cc && used[rr][cc - 1]))
          minn = (((minn) < (c[rr][cc])) ? (minn) : (c[rr][cc])),
          used[rr][cc] = 1;
        ++cc;
        --rr;
      }
      rr = i;
      cc = 0;
      while (rr >= 0) {
        if (c[rr][cc] != minn) used[rr][cc] = 0;
        ++cc;
        --rr;
      }
    } else {
      rr = n - 1;
      cc = i - rr;
      while (cc < n) {
        if ((rr && used[rr - 1][cc]) || (cc && used[rr][cc - 1]))
          minn = (((minn) < (c[rr][cc])) ? (minn) : (c[rr][cc])),
          used[rr][cc] = 1;
        --rr;
        ++cc;
      }
      rr = n - 1;
      cc = i - rr;
      while (rr >= 0) {
        if (c[rr][cc] != minn) used[rr][cc] = 0;
        ++cc;
        --rr;
      }
    }
    ans.push_back(minn);
  }
  cout << ans << endl;
  return 0;
}
