#include <bits/stdc++.h>
using namespace std;
inline int init() {
  int now = 0, ju = 1;
  char c;
  bool flag = false;
  while (1) {
    c = getchar();
    if (c == '-')
      ju = -1;
    else if (c >= '0' && c <= '9') {
      now = now * 10 + c - '0';
      flag = true;
    } else if (flag)
      return now * ju;
  }
}
inline long long llinit() {
  long long now = 0, ju = 1;
  char c;
  bool flag = false;
  while (1) {
    c = getchar();
    if (c == '-')
      ju = -1;
    else if (c >= '0' && c <= '9') {
      now = now * 10 + c - '0';
      flag = true;
    } else if (flag)
      return now * ju;
  }
}
struct node {
  int x, y;
};
queue<node> q;
int n, k;
bool vis[2005][2005];
char str[2005][2005];
int dp[2005][2005];
int nextx[2005][2005];
int nexty[2005][2005];
char ans[4005];
void bfs() {
  node now, o;
  int countermx = 0;
  while (!q.empty()) {
    now = q.front();
    q.pop();
    if (now.x > n || now.y > n || now.x < 1 || now.y < 1 ||
        vis[now.x][now.y] == 1 ||
        (dp[now.x][now.y] > k && ans[now.x + now.y - 1] < str[now.x][now.y]))
      continue;
    vis[now.x][now.y] = 1;
    if (now.x == 1 && now.y == 1 && str[now.x][now.y] <= ans[now.x + now.y - 1])
      ans[now.x + now.y - 1] = str[now.x][now.y];
    if (!vis[now.x + 1][now.y] && str[now.x + 1][now.y] <= ans[now.x + now.y] &&
        now.x < n) {
      ans[now.x + now.y] = str[now.x + 1][now.y];
      q.push((node){now.x + 1, now.y});
    }
    if (!vis[now.x][now.y + 1] && str[now.x][now.y + 1] <= ans[now.x + now.y] &&
        now.y < n) {
      ans[now.x + now.y] = str[now.x][now.y + 1];
      q.push((node){now.x, now.y + 1});
    }
  }
}
int main() {
  bool flag = false;
  node now, o;
  int maxx = 0, mx2 = 0;
  n = init();
  k = init();
  for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
  for (int i = 1; i <= 2 * n - 1; i++) {
    ans[i] = 'z';
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (str[i][j] != 'a') {
        if (i != 1 && j != 1)
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
        else if (i == 1)
          dp[i][j] = dp[i][j - 1] + 1;
        else
          dp[i][j] = dp[i - 1][j] + 1;
      } else {
        if (i != 1 && j != 1)
          dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
        else if (i == 1)
          dp[i][j] = dp[i][j - 1];
        else
          dp[i][j] = dp[i - 1][j];
      }
      if (dp[i][j] <= k) {
        mx2 = max(mx2, i + j - 1);
        maxx = max(maxx, dp[i][j]);
      }
    }
  }
  for (int i = 1; i <= mx2; i++) ans[i] = 'a';
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (dp[i][j] == maxx) q.push((node){i, j});
    }
  }
  if (q.size() == 0) q.push((node){1, 1});
  bfs();
  printf("%s", ans + 1);
  return 0;
}
