#include <bits/stdc++.h>
using namespace std;
inline int rei() {
  int x;
  cin >> x;
  return x;
}
inline long long rel() {
  long long x;
  cin >> x;
  return x;
}
inline string res() {
  string x;
  cin >> x;
  return x;
}
char Map[4000000];
int Kleft[4000000];
int From[4000000];
bool OK[4000000];
char ans[3999];
int sta[5000];
void Calc() {
  int N = rei();
  int K = rei();
  for (int i = 0; i < N; i++) {
    string S = res();
    for (int j = 0; j < N; j++) {
      Map[i * N + j] = S[j];
    }
  }
  Kleft[0] = K + 1;
  int maxa = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (Kleft[i * N + j]) {
        int d = -1;
        if (Map[i * N + j] == 'a') {
          d = 0;
        }
        if (i != N - 1) {
          if (Kleft[i * N + N + j] < Kleft[i * N + j] + d) {
            Kleft[i * N + N + j] = Kleft[i * N + j] + d;
            From[i * N + N + j] = i * N + j;
          }
        }
        if (j != N - 1) {
          if (Kleft[i * N + j + 1] < Kleft[i * N + j] + d) {
            Kleft[i * N + j + 1] = Kleft[i * N + j] + d;
            From[i * N + j + 1] = i * N + j;
          }
        }
        maxa = max(maxa, i + j);
      }
    }
  }
  if (Kleft[N * N - 1] > 1 ||
      (Kleft[N * N - 1] == 1 && Map[N * N - 1] == 'a')) {
    for (int i = 0; i < 2 * N - 1; i++) {
      cout << 'a';
    }
    cout << endl;
    return;
  }
  char m = 'z';
  int sp = 0;
  for (int i = 0; i <= maxa; i++) {
    int j = maxa - i;
    if (i < N && j < N && Kleft[i * N + j]) {
      if (Map[i * N + j] == m) {
        sta[sp++] = i * N + j;
      } else if (Map[i * N + j] < m) {
        m = Map[i * N + j];
        sp = 0;
        sta[sp++] = i * N + j;
      }
    }
  }
  for (int i = 0; i < sp; i++) {
    OK[sta[i]] = true;
  }
  for (int s = maxa + 1; s <= 2 * N - 2; s++) {
    sp = 0;
    m = 'z';
    for (int i = 0; i <= s; i++) {
      int j = s - i;
      if (i < N && j < N) {
        bool ok =
            (j != 0 && OK[i * N + j - 1]) || (i != 0 && OK[i * N + j - N]);
        if (j != 0 && OK[i * N + j - 1]) {
          From[i * N + j] = i * N + j - 1;
        }
        if (i != 0 && OK[i * N + j - N]) {
          From[i * N + j] = i * N + j - N;
        }
        if (ok) {
          if (Map[i * N + j] == m) {
            sta[sp++] = i * N + j;
          } else if (Map[i * N + j] < m) {
            m = Map[i * N + j];
            sp = 0;
            sta[sp++] = i * N + j;
          }
        }
      }
    }
    for (int i = 0; i < sp; i++) {
      OK[sta[i]] = true;
    }
  }
  {
    int xn = N - 1;
    int yn = N - 1;
    while (xn > 0 || yn > 0) {
      ans[xn + yn] = Map[yn * N + xn];
      int nxn = From[yn * N + xn] % N;
      int nyn = From[yn * N + xn] / N;
      xn = nxn;
      yn = nyn;
    }
    ans[0] = Map[0];
  }
  for (int i = 0; i < maxa; i++) {
    cout << 'a';
  }
  for (int i = maxa; i < 2 * N - 1; i++) {
    cout << ans[i];
  }
  cout << endl;
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(false), cin.tie(0);
  cout.tie(0);
  Calc();
  return 0;
}
