#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
string s[2000];
int D[2000][2000];
int vis[2000][2000];
pair<int, int> p[2000][2000];
int n, k;
string brute() {
  string z, bst;
  function<void(int, int, int)> dfs = [&](int i, int j, int k) {
    if (i == n || j == n) return;
    if (s[i][j] != 'a' && k)
      z.push_back('a'), k--;
    else
      z.push_back(s[i][j]);
    if (i == n - 1 && j == n - 1) {
      if (bst.empty())
        bst = z;
      else
        bst = min(bst, z);
    }
    dfs(i + 1, j, k);
    dfs(i, j + 1, k);
    z.pop_back();
  };
  dfs(0, 0, k);
  return bst;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> s[i];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) D[i][j] = 1e9;
  {
    deque<pair<int, int>> q;
    q.emplace_back(0, 0);
    D[0][0] = (s[0][0] != 'a');
    while (!q.empty()) {
      auto [i, j] = q.front();
      q.pop_front();
      if (vis[i][j]) continue;
      vis[i][j] = 1;
      if (i + 1 < n) {
        if (s[i + 1][j] == 'a') {
          D[i + 1][j] = min(D[i + 1][j], D[i][j]);
          q.emplace_front(i + 1, j);
        } else {
          D[i + 1][j] = min(D[i + 1][j], D[i][j] + 1);
          q.emplace_back(i + 1, j);
        }
      }
      if (j + 1 < n) {
        if (s[i][j + 1] == 'a') {
          D[i][j + 1] = min(D[i][j + 1], D[i][j]);
          q.emplace_front(i, j + 1);
        } else {
          D[i][j + 1] = min(D[i][j + 1], D[i][j] + 1);
          q.emplace_back(i, j + 1);
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
      }
    }
    string sol;
    vector<pair<int, int>> v, w;
    int md = -1e9;
    if (k == 0 && D[0][0]) {
      sol += s[0][0];
      v.emplace_back(0, 0);
      md = 0;
    } else {
      int x = 0, y = 0;
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          if (D[i][j] <= k) md = max(md, i + j);
      sol += string(md + 1, 'a');
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          if (D[i][j] <= k && i + j == md) v.emplace_back(i, j), s[i][j] = 'a';
    }
    memset(vis, 0, sizeof vis);
    while (!v.empty()) {
      char mc = 'z' + 1;
      for (auto [i, j] : v) mc = min(mc, s[i][j]);
      for (auto [i, j] : v) {
        if (s[i][j] != mc) continue;
        if (i + 1 < n && !vis[i + 1][j]) {
          p[i + 1][j] = {i, j};
          vis[i + 1][j] = 1;
          w.emplace_back(i + 1, j);
        }
        if (j + 1 < n && !vis[i][j + 1]) {
          p[i][j + 1] = {i, j};
          vis[i][j + 1] = 1;
          w.emplace_back(i, j + 1);
        }
      }
      swap(v, w);
      w.clear();
    }
    int i = n - 1, j = n - 1;
    string z;
    while (i + j != md) {
      z += s[i][j];
      tie(i, j) = p[i][j];
    }
    reverse(begin(z), end(z));
    sol += z;
    cout << sol;
  }
}
