#include <bits/stdc++.h>
using namespace std;
class vpc2 : public vector<vector<pair<char, char> > > {
 public:
  vpc2() : vector<vector<pair<char, char> > >(){};
  vpc2(int n, int m)
      : vector<vector<pair<char, char> > >(n, vector<pair<char, char> >(m)){};
  vpc2(int n, int m, pair<char, char> t)
      : vector<vector<pair<char, char> > >(n,
                                           vector<pair<char, char> >(m, t)){};
  vpc2(initializer_list<vector<pair<char, char> > > l)
      : vector<vector<pair<char, char> > >(l){};
};
class vpi2 : public vector<vector<pair<int, int> > > {
 public:
  vpi2() : vector<vector<pair<int, int> > >(){};
  vpi2(int n, int m)
      : vector<vector<pair<int, int> > >(n, vector<pair<int, int> >(m)){};
  vpi2(int n, int m, pair<int, int> t)
      : vector<vector<pair<int, int> > >(n, vector<pair<int, int> >(m, t)){};
  vpi2(initializer_list<vector<pair<int, int> > > l)
      : vector<vector<pair<int, int> > >(l){};
};
class vpll2 : public vector<vector<pair<long, long> > > {
 public:
  vpll2() : vector<vector<pair<long, long> > >(){};
  vpll2(int n, int m)
      : vector<vector<pair<long, long> > >(n, vector<pair<long, long> >(m)){};
  vpll2(int n, int m, pair<long, long> t)
      : vector<vector<pair<long, long> > >(n,
                                           vector<pair<long, long> >(m, t)){};
  vpll2(initializer_list<vector<pair<long, long> > > l)
      : vector<vector<pair<long, long> > >(l){};
};
class vc : public vector<char> {
 public:
  vc() : vector<char>(){};
  vc(int n) : vector<char>(n){};
  vc(int n, char t) : vector<char>(n, t){};
  vc(initializer_list<char> l) : vector<char>(l){};
  void scan() {
    string s;
    getline(cin, s);
    resize(s.length());
    for (unsigned int i = 0; i < s.length(); i++) (*this)[i] = s[i];
  }
  void print(string endl = "\n", string separate = "") {
    for (const char& u : *this) printf("%c%s", u, separate.c_str());
    printf("%s", endl.c_str());
  }
};
class vc2 : public vector<vc> {
 public:
  vc2() : vector<vc>(){};
  vc2(int n, int m) : vector<vc>(n, vc(m)){};
  vc2(int n, int m, char t) : vector<vc>(n, vc(m, t)){};
  vc2(initializer_list<vc> l) : vector<vc>(l){};
  void scan(int y) {
    resize(y);
    for (vc& u : *this) u.scan();
  }
  void print(string endl = "\n", string separate = "") {
    for (vc& u : *this) u.print(endl, separate);
  }
};
class vi : public vector<int> {
 public:
  vi() : vector<int>(){};
  vi(int n) : vector<int>(n){};
  vi(int n, int t) : vector<int>(n, t){};
  vi(initializer_list<int> l) : vector<int>(l){};
  void scan(int count) {
    resize(count);
    for (int i = 0; i < count; i++) scanf("%d", &((*this)[i]));
  }
  void print(string endl = "\n", string separate = " ") {
    for (const int& u : *this) printf("%d%s", u, separate.c_str());
    printf("%s", endl.c_str());
  }
};
class vi2 : public vector<vi> {
 public:
  vi2() : vector<vi>(){};
  vi2(int n, int m) : vector<vi>(n, vi(m)){};
  vi2(int n, int m, long long t) : vector<vi>(n, vi(m, t)){};
  vi2(initializer_list<vi> l) : vector<vi>(l){};
  void scan(int y, int x) {
    resize(y);
    for (vi& u : *this) u.scan(x);
  }
  void print(string endl = "\n", string separate = " ") {
    for (vi& u : *this) u.print(endl, separate);
  }
};
class vll : public vector<long long> {
 public:
  vll() : vector<long long>(){};
  vll(int n) : vector<long long>(n){};
  vll(int n, long long t) : vector<long long>(n, t){};
  vll(initializer_list<long long> l) : vector<long long>(l){};
  void scan(int count) {
    resize(count);
    for (int i = 0; i < count; i++) scanf("%I64d", &((*this)[i]));
  }
  void print(string endl = "\n", string separate = " ") {
    for (const long long& u : *this) printf("%I64d%s", u, separate.c_str());
    printf("%s", endl.c_str());
  }
};
class vll2 : public vector<vll> {
 public:
  vll2() : vector<vll>(){};
  vll2(int n, int m) : vector<vll>(n, vll(m)){};
  vll2(int n, int m, long long t) : vector<vll>(n, vll(m, t)){};
  vll2(initializer_list<vll> l) : vector<vll>(l){};
  void scan(int y, int x) {
    resize(y);
    for (vll& u : *this) u.scan(x);
  }
  void print(string endl = "\n", string separate = " ") {
    for (vll& u : *this) u.print(endl, separate);
  }
};
const int INF = INT_MAX;
const long long LINF = LLONG_MAX;
long long fpow(long long num, long long pow, long long mod) {
  if (pow == 0) return 1;
  long long l = fpow(num, pow / 2, mod);
  if (pow % 2 == 0)
    return l * l % mod;
  else
    return (l * l) % mod * num % mod;
}
long long gcd(long long a, long long b) {
  while (a != 0 && b != 0)
    if (a > b)
      a = a % b;
    else
      b = b % a;
  return a + b;
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
template <typename T>
T binary_search(T x, T start, T end, T (*func)(T), T e = 1) {
  while (end - start > e) {
    T mid = (start + end) / 2;
    if (func(mid) > x)
      end = mid;
    else
      start = mid;
  }
  return start;
}
long long cubll(long long x) { return x * x * x; }
long long sqrll(long long x) { return x * x; }
void solve();
int main() {
  srand(time(0));
  solve();
  return 0;
}
void solve() {
  int n, k;
  cin >> n >> k;
  string s;
  getline(cin, s);
  vc2 a;
  a.scan(n);
  if (a[0][0] != 'a' && k > 0) a[0][0] = 'a', k--;
  vi2 d(n, n, -1);
  d[0][0] = k;
  char ans[2 * n];
  ans[0] = a[0][0];
  ans[2 * n - 1] = 0;
  for (int i = 0; i < 2 * n - 2; i++) {
    char& opt = ans[i + 1];
    opt = 127;
    for (int x = 0; x < n; x++) {
      int y = i - x;
      if (y < 0 || y >= n) continue;
      if (d[y][x] == -1) continue;
      if (d[y][x] > 0) opt = 'a';
      if (x + 1 < n) opt = min(opt, a[y][x + 1]);
      if (y + 1 < n) opt = min(opt, a[y + 1][x]);
    }
    for (int x = 0; x < n; x++) {
      int y = i - x;
      if (y < 0 || y >= n) continue;
      if (d[y][x] == -1) continue;
      if (d[y][x] > 0) {
        if (x + 1 < n)
          d[y][x + 1] = max(d[y][x + 1], d[y][x] - (a[y][x + 1] != 'a'));
        if (y + 1 < n)
          d[y + 1][x] = max(d[y + 1][x], d[y][x] - (a[y + 1][x] != 'a'));
      } else {
        if (x + 1 < n && a[y][x + 1] == opt)
          d[y][x + 1] = max(d[y][x + 1], d[y][x]);
        if (y + 1 < n && a[y + 1][x] == opt)
          d[y + 1][x] = max(d[y + 1][x], d[y][x]);
      }
    }
  }
  cout << ans << endl;
}
