#include <bits/stdc++.h>
using namespace std;
long long int cons;
inline long long int check(long long int a) {
  if (a >= cons) a %= cons;
  return a;
}
inline long long int check2(long long int a) {
  a %= cons;
  if (a < 0) a += cons;
  return a;
}
inline long long int fast_check(long long int a) {
  if (a >= cons) a -= cons;
  return a;
}
long long int GCD(long long int a, long long int b) {
  while (a && b) {
    a = a % b;
    if (a != 0) b = b % a;
  }
  return a + b;
}
long long int exp(long long int a, long long int n) {
  long long int ans = 1;
  a = check(a);
  while (n) {
    if (n & 1) ans = check(ans * a);
    a = check(a * a);
    n = (n >> 1);
  }
  return ans;
}
void print_pair(pair<int, int> p) {
  cout << p.first << " " << p.second << "\n";
}
long long int nc2(long long int a) { return (a * (a - 1)) / 2; }
const int N = 2e3 + 10;
int dp[N][N];
int smallest = 'a';
int best[N][N][2];
int prev_k[N][N];
bool visited[N][N];
int newdp[N][N];
int n, k;
void process(pair<int, int> a, int k, int curx, int cury,
             vector<pair<int, int>> &aa) {
  int cur = dp[a.first][a.second];
  int newk = k;
  if (cur != smallest && newk) cur = smallest, newk--;
  if (!visited[a.first][a.second]) {
    visited[a.first][a.second] = true;
    best[a.first][a.second][0] = curx;
    best[a.first][a.second][1] = cury;
    aa.push_back({a.first, a.second});
    newdp[a.first][a.second] = cur;
    prev_k[a.first][a.second] = newk;
  } else {
    if (cur < newdp[a.first][a.second]) {
      newdp[a.first][a.second] = cur;
      prev_k[a.first][a.second] = newk;
      best[a.first][a.second][0] = curx;
      best[a.first][a.second][1] = cury;
    } else if (prev_k[a.first][a.second] < newk) {
      prev_k[a.first][a.second] = newk;
      best[a.first][a.second][0] = curx;
      best[a.first][a.second][1] = cury;
    }
  }
}
void checker(int first, int second, int curx, int cury, int ch,
             vector<pair<int, int>> &aa) {
  if (first > 0 && second > 0 && first <= n && second <= n)
    process({first, second}, ch, curx, cury, aa);
}
bool C(pair<int, int> a, pair<int, int> b) {
  return newdp[a.first][a.second] < newdp[b.first][b.second];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cons = 1e9 + 7;
  srand(time(NULL));
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      char c;
      cin >> c;
      dp[i][j] = c;
    }
  }
  vector<pair<int, int>> a, b;
  process({1, 1}, k, 0, 0, a);
  while (a.size()) {
    for (auto itr : a) {
      checker(itr.first + 1, itr.second, itr.first, itr.second,
              prev_k[itr.first][itr.second], b);
      checker(itr.first, itr.second + 1, itr.first, itr.second,
              prev_k[itr.first][itr.second], b);
    }
    a.clear();
    sort(b.begin(), b.end(), C);
    int xx = b.size();
    if (xx == 0) break;
    a.push_back(b[0]);
    for (int i = 1; i < xx; i++) {
      if (newdp[b[i].first][b[i].second] !=
          newdp[b[i - 1].first][b[i - 1].second])
        break;
      a.push_back(b[i]);
    }
    b.clear();
  }
  vector<int> ans;
  int curx = n, cury = n;
  while (curx) {
    ans.push_back(newdp[curx][cury]);
    int temp = curx;
    curx = best[curx][cury][0];
    cury = best[temp][cury][1];
  }
  int second = ans.size();
  second--;
  while (second >= 0) {
    cout << (char)ans[second--];
  }
  return 0;
}
