#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
const long long NMAX = 2011;
char p[NMAX][NMAX];
int dp[NMAX][NMAX];
int ans[NMAX][NMAX];
int used[NMAX][NMAX];
signed main() {
  cin.tie(0);
  cout.tie(0);
  cin.sync_with_stdio(0);
  cout.sync_with_stdio(0);
  int n;
  cin >> n;
  int m = n;
  int k;
  cin >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      cin >> p[i][j];
    }
  for (int i = 0; i <= n; i++) dp[i][0] = inf;
  for (int i = 0; i <= m; i++) dp[0][i] = inf;
  dp[0][1] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (p[i][j] == 'a') {
        if (dp[i - 1][j] > dp[i][j - 1]) {
          dp[i][j] = dp[i][j - 1];
          ans[i][j] = 0;
        } else {
          dp[i][j] = dp[i - 1][j];
          ans[i][j] = 1;
        }
      } else {
        if (dp[i - 1][j] > dp[i][j - 1]) {
          dp[i][j] = dp[i][j - 1] + 1;
          ans[i][j] = 0;
        } else {
          dp[i][j] = dp[i - 1][j] + 1;
          ans[i][j] = 1;
        }
      }
    }
  }
  queue<pair<long long, long long> > q;
  int fl = 0;
  for (int i = n + m; i >= 2 && !fl; i--) {
    for (int j = 1; i - j >= 1; j++) {
      if (j <= n && i - j <= m) {
        if (dp[j][i - j] <= k) {
          fl = 1;
          q.push({j, i - j});
        }
      }
    }
  }
  if (!fl) q.push({1, 1});
  while (!used[n][m]) {
    queue<pair<long long, long long> > w;
    char cur = 'z';
    while (!q.empty()) {
      int x = q.front().first;
      int y = q.front().second;
      q.pop();
      if (!used[x][y]) {
        used[x][y] = 1;
        if (x != n) {
          if (p[x + 1][y] < cur) {
            while (!w.empty()) w.pop();
            w.push({x + 1, y});
            ans[x + 1][y] = 1;
            cur = p[x + 1][y];
          } else if (p[x + 1][y] == cur) {
            w.push({x + 1, y});
            ans[x + 1][y] = 1;
          }
        }
        if (y != m) {
          if (p[x][y + 1] < cur) {
            while (!w.empty()) w.pop();
            w.push({x, y + 1});
            ans[x][y + 1] = 0;
            cur = p[x][y + 1];
          } else if (p[x][y + 1] == cur) {
            w.push({x, y + 1});
            ans[x][y + 1] = 0;
          }
        }
      }
    }
    q = w;
  }
  string res;
  int x = n;
  int y = m;
  while (x != 1 || y != 1) {
    res.push_back(p[x][y]);
    if (ans[x][y])
      x--;
    else
      y--;
  }
  res.push_back(p[1][1]);
  reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); i++) {
    if (res[i] != 'a' && k > 0) {
      res[i] = 'a';
      k--;
    }
  }
  cout << res;
  return 0;
}
