#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;
const long double EPS = 1e-9;
const int MOD = 1000000007;
const long long LLINF = 1000000000000000001;
const int maxn = 2042;
int n, k;
char a[maxn][maxn];
bool seen[maxn][maxn];
vector<char> ans;
queue<pair<int, int> > gque1;
queue<pair<int, int> > gque2;
queue<pair<int, int> > *q1 = &gque1;
queue<pair<int, int> > *q2 = &gque2;
void finishclear() {
  for (int i = 1; i <= 2 * n - 1; i++) cout << 'a';
  cout << '\n';
  exit(0);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cin >> a[i][j];
  q1->push({1, 1});
  if (k > 0) {
    if (a[1][1] != 'a') k--;
    while (k > 0) {
      while (!q1->empty()) {
        auto z = q1->front();
        q1->pop();
        if (z.first == n && z.second == n) finishclear();
        if (z.first + 1 <= n && !seen[z.first + 1][z.second]) {
          seen[z.first + 1][z.second] = true;
          if (a[z.first + 1][z.second] == 'a')
            q1->push({z.first + 1, z.second});
          else
            q2->push({z.first + 1, z.second});
        }
        if (z.second + 1 <= n && !seen[z.first][z.second + 1]) {
          seen[z.first][z.second + 1] = true;
          if (a[z.first][z.second + 1] == 'a')
            q1->push({z.first, z.second + 1});
          else
            q2->push({z.first, z.second + 1});
        }
      }
      swap(q1, q2);
      k--;
    }
    while (!q1->empty()) {
      auto z = q1->front();
      q1->pop();
      q2->push(z);
      if (z.first + 1 <= n && !seen[z.first + 1][z.second]) {
        if (a[z.first + 1][z.second] == 'a') {
          q1->push({z.first + 1, z.second});
          seen[z.first + 1][z.second] = true;
        }
      }
      if (z.second + 1 <= n && !seen[z.first][z.second + 1]) {
        if (a[z.first][z.second + 1] == 'a') {
          q1->push({z.first, z.second + 1});
          seen[z.first][z.second + 1] = true;
        }
      }
    }
    swap(q1, q2);
    if (q1->empty()) {
      finishclear();
    }
    int maxdst = 0;
    while (!q1->empty()) {
      auto z = q1->front();
      q2->push(z);
      maxdst = max(maxdst, z.first + z.second);
      q1->pop();
    }
    swap(q1, q2);
    while (!q1->empty()) {
      auto z = q1->front();
      if (z.first + z.second == maxdst) q2->push(z);
      q1->pop();
    }
    swap(q1, q2);
    for (int i = 1; i <= maxdst - 1; i++) ans.push_back('a');
  } else
    ans.push_back(a[1][1]);
  while (((int)(ans).size()) < 2 * n - 1) {
    char nextchar = 'z';
    while (!q1->empty()) {
      auto z = q1->front();
      q1->pop();
      q2->push(z);
      if (z.first + 1 <= n) nextchar = min(nextchar, a[z.first + 1][z.second]);
      if (z.second + 1 <= n) nextchar = min(nextchar, a[z.first][z.second + 1]);
    }
    swap(q1, q2);
    ans.push_back(nextchar);
    while (!q1->empty()) {
      auto z = q1->front();
      q1->pop();
      if (z.first + 1 <= n && !seen[z.first + 1][z.second] &&
          a[z.first + 1][z.second] == nextchar) {
        seen[z.first + 1][z.second] = true;
        q2->push({z.first + 1, z.second});
      }
      if (z.second + 1 <= n && !seen[z.first][z.second + 1] &&
          a[z.first][z.second + 1] == nextchar) {
        seen[z.first][z.second + 1] = true;
        q2->push({z.first, z.second + 1});
      }
    }
    swap(q1, q2);
  }
  for (auto i : ans) cout << i;
  cout << '\n';
}
