#include <bits/stdc++.h>
using namespace std;
const long long inf = 2e18;
const int N = 2e3 + 10;
const int dx[] = {0, 1};
const int dy[] = {1, 0};
long long add(long long x, long long y) {
  if (x + y > inf) {
    return inf;
  }
  return x + y;
}
long long mul(long long x, long long y) {
  if (x > inf / y) return inf;
  return x * y;
}
struct Point {
  int x, y;
  Point(int x, int y) : x(x), y(y) {}
  Point() {}
};
vector<char> s[N], res;
int Minm[N][N];
int n, m, k;
queue<Point> q;
Point nxt[N * N];
int tail, minm;
Point cur;
int main() {
  scanf("%d%d", &n, &k);
  m = n;
  for (int i = 1; i <= n; i++) {
    s[i].resize(m + 1);
    for (int j = 1; j <= m; j++) {
      s[i][j] = getchar();
      while (s[i][j] < 'a' || s[i][j] > 'z') s[i][j] = getchar();
    }
  }
  if (n == 1) {
    if (s[1][1] == 'a' || k)
      cout << 'a';
    else
      cout << s[1][1];
    return 0;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      if (i == 1 && j == 1) {
        Minm[i][j] = s[1][1] != 'a';
      } else {
        Minm[i][j] = min(i > 1 ? Minm[i - 1][j] : n * n,
                         j > 1 ? Minm[i][j - 1] : n * n) +
                     (s[i][j] != 'a');
      }
    }
  if (k >= Minm[n][n]) {
    for (int i = 1; i < 2 * n; i++) cout << 'a';
    return 0;
  } else {
    int Long = -1;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (Minm[i][j] == k) {
          Long = max(Long, i + j - 2);
        }
      }
    }
    for (int i = 0; i <= Long; i++) res.push_back('a');
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) {
        if (Minm[i][j] == k && i + j - 2 == Long) {
          q.push(Point(i, j));
        }
      }
  }
  if (!q.size()) {
    res.push_back(s[1][1]);
    q.push(Point(1, 1));
  }
  while (cur.x != n || cur.y != m) {
    for (int step = 1;; step++) {
      minm = 26;
      tail = 0;
      while (q.size()) {
        Point now = q.front();
        q.pop();
        for (int i = 0; i < 2; i++) {
          int nx = now.x + dx[i], ny = now.y + dy[i];
          if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
          nxt[++tail] = Point(nx, ny);
        }
      }
      int Tail = 0;
      for (int i = 1; i <= tail; i++) {
        int j = i;
        while (j + 1 <= tail && nxt[j + 1].x == nxt[i].x &&
               nxt[j + 1].y == nxt[i].y)
          j++;
        nxt[++Tail] = Point(nxt[i].x, nxt[i].y);
        minm = min(minm, s[nxt[i].x][nxt[i].y] - 'a');
        i = j;
      }
      res.push_back(minm + 'a');
      for (int j = 1; j <= Tail; j++) {
        if (s[nxt[j].x][nxt[j].y] - 'a' == minm) {
          q.push(nxt[j]);
        }
      }
      if (q.size() == 1) {
        cur = q.front();
        break;
      }
    }
  }
  for (size_t i = 0; i < res.size(); i++) putchar(res[i]);
  return 0;
}
