#include <bits/stdc++.h>
const int maxn = 2e3 + 7;
class Solution {
 private:
  int n, k, cnt;
  char s[maxn][maxn];
  int f[maxn][maxn];
  bool vis[maxn][maxn];
  char ans[maxn * 2];
  int tot;
  struct Node {
    int x, y;
    Node(int x, int y) : x(x), y(y) {}
  };
  int now, last;
  std ::queue<Node> q[2], tmp;
  void Make() {
    for (register int i = 1; i + cnt < n + n; i++) {
      char z = 'z' + 1;
      while (!q[last].empty()) {
        Node nd = q[last].front();
        tmp.push(nd);
        q[last].pop();
        if (nd.x < n) {
          z = std ::min(z, s[nd.x + 1][nd.y]);
        }
        if (nd.y < n) {
          z = std ::min(z, s[nd.x][nd.y + 1]);
        }
      }
      while (!tmp.empty()) {
        Node nd = tmp.front();
        tmp.pop();
        if (nd.x < n) {
          if (s[nd.x + 1][nd.y] == z && !vis[nd.x + 1][nd.y]) {
            vis[nd.x + 1][nd.y] = 1;
            q[now].push(Node(nd.x + 1, nd.y));
          }
        }
        if (nd.y < n) {
          if (s[nd.x][nd.y + 1] == z && !vis[nd.x][nd.y + 1]) {
            vis[nd.x][nd.y + 1] = 1;
            q[now].push(Node(nd.x, nd.y + 1));
          }
        }
      }
      std ::swap(now, last);
    }
  }
  void DFS(int x, int y) {
    if (x <= 0 || y <= 0) {
      return;
    }
    if (x + y == cnt) {
      return;
    }
    ans[++tot] = s[x][y];
    if (vis[x - 1][y]) {
      DFS(x - 1, y);
    } else {
      DFS(x, y - 1);
    }
  }

 public:
  Solution() {
    now = 1;
    last = 0;
    Get();
    Solve();
  }
  void Get() {
    scanf("%d %d", &n, &k);
    for (register int i = 1; i <= n; i++) {
      scanf("%s", s[i] + 1);
    }
  }
  void Solve() {
    memset(f, 0x3f, sizeof(f));
    f[1][1] = s[1][1] == 'a' ? 0 : 1;
    for (register int i = 1; i <= n; i++) {
      for (register int j = 1; j <= n; j++) {
        if (i == 1 && j == 1) {
          continue;
        }
        f[i][j] = std ::min(f[i - 1][j], f[i][j - 1]);
        if (s[i][j] != 'a') {
          f[i][j]++;
        }
      }
    }
    for (register int i = 1; i <= n; i++) {
      for (register int j = 1; j <= n; j++) {
        if (f[i][j] <= k && i + j > cnt) {
          cnt = i + j;
        }
      }
    }
    for (register int i = 1; i <= n; i++) {
      for (register int j = 1; j <= n; j++) {
        if (i + j == cnt && f[i][j] <= k) {
          vis[i][j] = 1;
          q[last].push(Node(i, j));
        }
      }
    }
    if (q[last].empty()) {
      vis[1][1] = 1;
      q[last].push(Node(1, 1));
    }
    Make();
    DFS(n, n);
    for (register int i = 1; i < cnt; i++) putchar('a');
    for (register int i = tot; i >= 1; i--) putchar(ans[i]);
    putchar('\n');
  }
};
Solution sol;
int main() {}
