#include <bits/stdc++.h>
using namespace std;
int read() {
  char c = getchar();
  int f = 1, sum = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * f;
}
vector<pair<int, int> > v[2];
vector<char> writeout;
int dis[2010][2010], vis[2010][2010];
pair<int, int> pre[2010][2010];
deque<pair<int, int> > q;
char c[2010][2010];
int main() {
  int n, m, yeshou = 0, ans = 0;
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
  v[0].push_back(pair<int, int>(1, 1));
  dis[1][1] = (c[1][1] != 'a');
  if (dis[1][1] <= m) q.push_back(pair<int, int>(1, 1));
  while (!q.empty()) {
    int x = q.front().first, y = q.front().second;
    q.pop_front();
    if (x == n && y == n) {
      for (int i = 1; i <= n + n - 1; i++) putchar('a');
      return 0;
    }
    if (dis[x][y] == m) {
      if (x + y - 1 > ans)
        ans = x + y - 1, v[0].clear(), v[0].push_back(pair<int, int>(x, y));
      else if (x + y - 1 == ans)
        v[0].push_back(pair<int, int>(x, y));
    }
    if (x + 1 <= n && !vis[x + 1][y]) {
      if (c[x + 1][y] == 'a') {
        dis[x + 1][y] = dis[x][y];
        vis[x + 1][y] = 1;
        q.push_front(pair<int, int>(x + 1, y));
      } else if (dis[x][y] != m) {
        dis[x + 1][y] = dis[x][y] + 1;
        vis[x + 1][y] = 1;
        q.push_back(pair<int, int>(x + 1, y));
      }
    }
    if (y + 1 <= n && !vis[x][y + 1]) {
      if (c[x][y + 1] == 'a') {
        dis[x][y + 1] = dis[x][y];
        vis[x][y + 1] = 1;
        q.push_front(pair<int, int>(x, y + 1));
      } else if (dis[x][y] != m) {
        dis[x][y + 1] = dis[x][y] + 1;
        vis[x][y + 1] = 1;
        q.push_back(pair<int, int>(x, y + 1));
      }
    }
  }
  for (;; yeshou ^= 1) {
    v[yeshou ^ 1].clear();
    for (int i = 0; i < 26; i++) {
      bool flag = 0;
      for (auto fuck : v[yeshou]) {
        int x = fuck.first, y = fuck.second;
        if (x == n && y == n) goto wtf;
        if (x + 1 <= n && c[x + 1][y] - 'a' == i && !vis[x + 1][y]) {
          flag = 1;
          v[yeshou ^ 1].push_back(pair<int, int>(x + 1, y));
          vis[x + 1][y] = 1;
          pre[x + 1][y] = pair<int, int>(x, y);
        }
        if (y + 1 <= n && c[x][y + 1] - 'a' == i && !vis[x][y + 1]) {
          flag = 1;
          v[yeshou ^ 1].push_back(pair<int, int>(x, y + 1));
          vis[x][y + 1] = 1;
          pre[x][y + 1] = pair<int, int>(x, y);
        }
      }
      if (flag) break;
    }
  }
wtf:;
  int x = n, y = n;
  for (int i = n + n - 1; i > ans; i--) {
    writeout.push_back(c[x][y]);
    int tmp = x;
    x = pre[x][y].first;
    y = pre[tmp][y].second;
  }
  for (int i = 1; i <= ans; i++) putchar('a');
  reverse(writeout.begin(), writeout.end());
  for (auto ch : writeout) putchar(ch);
  return 0;
}
