#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  vector<string> mat;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    mat.push_back(s);
  }
  vector<int> row(n, 1000000000);
  vector<vector<int>> dp(n, row);
  if (mat[0][0] == 'a')
    dp[0][0] = 0;
  else
    dp[0][0] = 1;
  for (int i = 1; i <= n - 1; i++) {
    for (int j = 0; j <= i; j++) {
      int row = i - j;
      int col = j;
      if (row >= 1) dp[row][col] = min(dp[row - 1][col], dp[row][col]);
      if (col >= 1) dp[row][col] = min(dp[row][col - 1], dp[row][col]);
      if (mat[row][col] != 'a') dp[row][col]++;
    }
  }
  for (int i = n; i <= 2 * n - 2; i++) {
    for (int j = i - n + 1; j <= n - 1; j++) {
      int col = j;
      int row = i - col;
      if (row >= 1) dp[row][col] = min(dp[row - 1][col], dp[row][col]);
      if (col >= 1) dp[row][col] = min(dp[row][col - 1], dp[row][col]);
      if (mat[row][col] != 'a') dp[row][col]++;
    }
  }
  if (dp[n - 1][n - 1] <= k) {
    string ans(2 * n - 1, 'a');
    cout << ans << endl;
    return 0;
  }
  int flag = 0;
  set<pair<int, int>> pirs;
  int tot = -1;
  for (int i = 2 * n - 2; i >= n; i--) {
    for (int j = i - n + 1; j <= n - 1; j++) {
      int col = j;
      int row = i - j;
      if (dp[row][col] == k) {
        tot = i;
        pirs.insert({row, col});
        flag = 1;
      }
    }
    if (flag) break;
  }
  if (!flag) {
    for (int i = n - 1; i >= 0; i--) {
      for (int j = 0; j <= i; j++) {
        int row = i - j;
        int col = j;
        if (dp[row][col] == k) {
          tot = i;
          pirs.insert({row, col});
          flag = 1;
        }
      }
      if (flag) break;
    }
  }
  string ans;
  if (tot == -1) {
    ans.push_back(mat[0][0]);
    pirs.insert({0, 0});
    tot = 0;
  } else
    for (int i = 0; i <= tot; i++) ans.push_back('a');
  while (tot < 2 * n - 2) {
    set<pair<int, int>> pirs2;
    int val = 1000000000;
    for (auto it = pirs.begin(); it != pirs.end(); it++) {
      if (it->first + 1 < n)
        val = min(val, mat[it->first + 1][it->second] - 'a');
      if (it->second + 1 < n)
        val = min(val, mat[it->first][it->second + 1] - 'a');
    }
    ans.push_back('a' + val);
    for (auto it = pirs.begin(); it != pirs.end(); it++) {
      if (it->first + 1 < n) {
        if (mat[it->first + 1][it->second] - 'a' == val &&
            !pirs2.count({it->first + 1, it->second}))
          pirs2.insert({it->first + 1, it->second});
      }
      if (it->second + 1 < n) {
        if (mat[it->first][it->second + 1] - 'a' == val &&
            !pirs2.count({it->first, it->second + 1}))
          pirs2.insert({it->first, it->second + 1});
      }
    }
    pirs = pirs2;
    tot++;
  }
  cout << ans << endl;
  return 0;
}
