#include <bits/stdc++.h>
using namespace std;
struct Node {
  int x, y;
} temp, wtf;
char s[2005][2005];
int dp[2005][2005];
queue<Node> q[2];
string ans, now;
bool life[2005][2005];
int main() {
  int n, k;
  int flag = -1;
  bool gg;
  string ans;
  char now;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
  if (s[1][1] != 'a') dp[1][1] = 1;
  if (dp[1][1] <= k) flag = 2;
  for (int i = 3; i <= n * 2; i++) {
    for (int j = max(1, i - n); j < i && j <= n; j++) {
      if (j == 1)
        dp[j][i - j] = dp[j][i - j - 1];
      else {
        dp[j][i - j] = dp[j - 1][i - j];
        if (i - j > 1) dp[j][i - j] = min(dp[j][i - j], dp[j][i - j - 1]);
      }
      if (s[j][i - j] != 'a') dp[j][i - j]++;
      if (dp[j][i - j] <= k) flag = i;
    }
  }
  if (flag == -1) {
    ans = "";
    temp.x = 1;
    temp.y = 1;
    gg = 0;
    q[0].push(temp);
    flag = 1;
    ans += s[1][1];
    while (flag < 2 * n - 1) {
      flag++;
      now = 'z';
      while (!q[gg].empty()) {
        temp = q[gg].front();
        q[gg].pop();
        wtf.x = temp.x;
        wtf.y = temp.y + 1;
        if (wtf.y <= n && !life[wtf.x][wtf.y]) {
          if (s[wtf.x][wtf.y] < now) {
            now = s[wtf.x][wtf.y];
            while (!q[!gg].empty()) q[!gg].pop();
          }
          if (s[wtf.x][wtf.y] == now) q[!gg].push(wtf);
          life[wtf.x][wtf.y] = 1;
        }
        wtf.x = temp.x + 1;
        wtf.y = temp.y;
        if (wtf.x <= n && !life[wtf.x][wtf.y]) {
          if (s[wtf.x][wtf.y] < now) {
            now = s[wtf.x][wtf.y];
            while (!q[!gg].empty()) q[!gg].pop();
          }
          if (s[wtf.x][wtf.y] == now) q[!gg].push(wtf);
          life[wtf.x][wtf.y] = 1;
        }
      }
      ans += now;
      gg = !gg;
    }
  } else {
    ans = "";
    for (int i = 2; i <= flag; i++) ans += 'a';
    if (flag != 2 * n) {
      now = 'z';
      gg = 0;
      for (int i = max(1, flag - n); i <= n && i < flag; i++) {
        if (dp[i][flag - i] > k) continue;
        temp.x = i;
        temp.y = flag + 1 - i;
        if (temp.y <= n && !life[temp.x][temp.y]) {
          if (s[temp.x][temp.y] < now) {
            now = s[temp.x][temp.y];
            while (!q[gg].empty()) q[gg].pop();
          }
          if (s[temp.x][temp.y] == now) q[gg].push(temp);
          life[temp.x][temp.y] = 1;
        }
        temp.x = i + 1;
        temp.y = flag - i;
        if (temp.x <= n && !life[temp.x][temp.y]) {
          if (s[temp.x][temp.y] < now) {
            now = s[temp.x][temp.y];
            while (!q[gg].empty()) q[gg].pop();
          }
          if (s[temp.x][temp.y] == now) q[gg].push(temp);
          life[temp.x][temp.y] = 1;
        }
      }
      ans += now;
      while (flag < 2 * n - 1) {
        flag++;
        now = 'z';
        while (!q[gg].empty()) {
          temp = q[gg].front();
          q[gg].pop();
          wtf.x = temp.x;
          wtf.y = temp.y + 1;
          if (wtf.y <= n && !life[wtf.x][wtf.y]) {
            if (s[wtf.x][wtf.y] < now) {
              now = s[wtf.x][wtf.y];
              while (!q[!gg].empty()) q[!gg].pop();
            }
            if (s[wtf.x][wtf.y] == now) q[!gg].push(wtf);
            life[wtf.x][wtf.y] = 1;
          }
          wtf.x = temp.x + 1;
          wtf.y = temp.y;
          if (wtf.x <= n && !life[wtf.x][wtf.y]) {
            if (s[wtf.x][wtf.y] < now) {
              now = s[wtf.x][wtf.y];
              while (!q[!gg].empty()) q[!gg].pop();
            }
            if (s[wtf.x][wtf.y] == now) q[!gg].push(wtf);
            life[wtf.x][wtf.y] = 1;
          }
        }
        ans += now;
        gg = !gg;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
