#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
char c[2005][2005];
bool h[2005][2005];
int cs[2005][2005];
char l[2005][2005];
string s;
int main() {
  ios::sync_with_stdio(false);
  int n, w;
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> c[i][j];
    }
  }
  if (c[0][0] != 'a' && w >= 1) {
    cs[0][0]++;
    c[0][0] = 'a';
  }
  s += c[0][0];
  for (int k = 1; k <= 2 * n - 2; k++) {
    char be = 'z';
    for (int i = 0; i <= k; i++) {
      int j = k - i;
      if (j >= n || i >= n) continue;
      if (i - 1 < 0 || h[i - 1][j]) {
        if (j - 1 < 0 || h[i][j - 1]) {
          h[i][j] = true;
          continue;
        } else {
          if (c[i][j] == 'a') {
            be = 'a';
            l[i][j] = 'a';
            cs[i][j] = cs[i][j - 1];
          } else {
            if (cs[i][j - 1] < w) {
              be = 'a';
              l[i][j] = 'a';
              cs[i][j] = cs[i][j - 1] + 1;
            } else {
              l[i][j] = c[i][j];
              if (c[i][j] < be) be = c[i][j];
              cs[i][j] = cs[i][j - 1];
            }
          }
        }
        continue;
      }
      if (j - 1 < 0 || h[i][j - 1]) {
        if (c[i][j] == 'a') {
          be = 'a';
          l[i][j] = 'a';
          cs[i][j] = cs[i - 1][j];
        } else {
          if (cs[i - 1][j] < w) {
            be = 'a';
            l[i][j] = 'a';
            cs[i][j] = cs[i - 1][j] + 1;
          } else {
            l[i][j] = c[i][j];
            if (c[i][j] < be) be = c[i][j];
            cs[i][j] = cs[i - 1][j];
          }
        }
        continue;
      }
      if (c[i][j] == 'a') {
        be = 'a';
        l[i][j] = 'a';
        cs[i][j] = min(cs[i][j - 1], cs[i - 1][j]);
      } else {
        if (min(cs[i][j - 1], cs[i - 1][j]) < w) {
          be = 'a';
          l[i][j] = 'a';
          cs[i][j] = min(cs[i][j - 1], cs[i - 1][j]) + 1;
        } else {
          l[i][j] = c[i][j];
          if (c[i][j] < be) be = c[i][j];
          cs[i][j] = cs[i][j - 1];
        }
      }
    }
    for (int i = 0; i <= k; i++) {
      int j = k - i;
      if (j >= n || i >= n) continue;
      if (l[i][j] != be) h[i][j] = true;
    }
    s += be;
  }
  cout << s;
}
