#include <bits/stdc++.h>
using namespace std;
template <typename Tp>
inline void outarr(Tp _array, const std::size_t _N, const char* _delim = " ") {
  Tp end = std::next(_array, _N);
  for (Tp current = _array; current != end; ++current) {
    std::cout << *current << _delim;
  }
  std::cout << '\n';
}
using ll = int64_t;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<const int>(1e9 + 7);
string gr[2000];
int dp[2000][2000];
int cur[2000];
void GetAns(int n) {
  int L = 0;
  for (int i = n - 1; i >= L; --i) {
    int j = cur[i];
    if (j == -1) {
      continue;
    }
    if (j + 1 < n) {
      ++cur[i];
    } else {
      cur[i] = -1;
    }
    if (i + 1 < n) {
      cur[i + 1] = j;
    }
  }
  for (;;) {
    char minc = 'z' + 1;
    int pre = L;
    for (int i = n - 1; i >= pre; --i) {
      int j = cur[i];
      if (j == -1) {
        continue;
      }
      L = i;
      minc = min(gr[i][j], minc);
    }
    for (int i = n - 1; i >= L; --i) {
      int j = cur[i];
      if (j == -1) {
        continue;
      }
      if (gr[i][j] != minc) {
        cur[i] = -1;
        continue;
      }
      if (j + 1 < n) {
        ++cur[i];
      } else {
        cur[i] = -1;
      }
      if (i + 1 < n) {
        cur[i + 1] = j;
      }
    }
    if (minc > 'z') {
      break;
    }
    cout << minc;
  }
  cout << "\n";
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < (n); ++i) {
    cin >> gr[i];
  }
  memset(cur, -1, sizeof(cur));
  if (k == 0) {
    cout << gr[0][0];
    cur[0] = 0;
    GetAns(n);
    return 0;
  }
  dp[0][0] = gr[0][0] == 'a';
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (i) {
        dp[i][j] = max(dp[i - 1][j] + (gr[i][j] == 'a'), dp[i][j]);
      }
      if (j) {
        dp[i][j] = max(dp[i][j - 1] + (gr[i][j] == 'a'), dp[i][j]);
      }
    }
  }
  int maxPref = 0;
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (i + j + 1 - dp[i][j] <= k) {
        maxPref = max(maxPref, i + j);
      }
    }
  }
  cout << string(maxPref + 1, 'a');
  for (int i = max(0, maxPref - n + 1); i <= min(n, maxPref); ++i) {
    int j = maxPref - i;
    if (maxPref + 1 - dp[i][j] <= k) {
      cur[i] = j;
    }
  }
  GetAns(n);
  return 0;
}
