#include <bits/stdc++.h>   using namespace std;   void qmax(int &x, int y) {     if (x < y) x = y;   }   void qmin(int &x, int y) {     if (x > y) x = y;   }   inline long long read() {     char s;     long long k = 0, base = 1;     while ((s = getchar()) !=  -  && s != EOF && !(isdigit(s)))       ;     if (s == EOF) exit(0);     if (s ==  - ) base = -1, s = getchar();     while (isdigit(s)) {       k = k * 10 + (s ^  0 );       s = getchar();     }     return k * base;   }   inline void write(int x) {     static char cnt, num[15];     cnt = 0;     if (!x) {       printf( 0 );       return;     }     for (; x; x /= 10) num[++cnt] = x % 10;     for (; cnt; putchar(num[cnt--] + 48))       ;   }   const int maxn = 2020;   int n, k;   char ch[maxn][maxn];   int a[maxn][maxn], Max;   char d[maxn + maxn];   bool vis[maxn][maxn];   int main() {     n = read();     k = read();     for (int i = 1; i <= n; i++) {       scanf( %s , ch[i] + 1);     }     if (k >= (2 * n - 1)) {       for (int i = 1; i <= n + n - 1; i++) putchar( a );       return 0;     }     memset(a, 0x3f3f, sizeof(a));     a[1][1] = 1;     if (ch[1][1] ==  a ) a[1][1] = 0;     for (int l = 2; l <= n + n; l++) {       for (int i = 1, j; i <= n; i++) {         j = l - i;         if (j <= 0) break;         if (j > n) continue;         if (i > n) continue;         if (j + 1 <= n) qmin(a[i][j + 1], a[i][j] + (ch[i][j + 1] !=  a ));         if (i + 1 <= n) qmin(a[i + 1][j], a[i][j] + (ch[i + 1][j] !=  a ));         if (a[i][j] <= k) Max = max(Max, l);       }     }     if (Max == n + n) {       for (int i = 1; i <= n + n - 1; i++) putchar( a );       return 0;     }     bool flag = false;     if (!Max) Max = 2, vis[1][1] = true, d[2] = ch[1][1], flag = true;     for (int i = 1, j; i <= n; i++) {       j = Max - i;       if (j <= 0) break;       if (j > n) continue;       if (a[i][j] <= k) vis[i][j] = true;     }     for (int l = Max; l <= n + n; l++) {       char z =  z ;       for (int i = 1, j; i <= n; i++) {         j = l - i;         if (j <= 0) break;         if (j > n) continue;         if (!vis[i][j]) continue;         if (j + 1 <= n) z = min(z, ch[i][j + 1]);         if (i + 1 <= n) z = min(z, ch[i + 1][j]);       }       d[l + 1] = z;       for (int i = 1, j; i <= n; i++) {         j = l - i;         if (j <= 0) break;         if (j > n) continue;         if (!vis[i][j]) continue;         if (j + 1 <= n && ch[i][j + 1] == z) vis[i][j + 1] = true;         if (i + 1 <= n && ch[i + 1][j] == z) vis[i + 1][j] = true;       }     }     if (flag) Max--;     for (int i = 2; i <= Max; i++) d[i] =  a ;     for (int i = 2; i <= n + n; i++) {       putchar(d[i]);     }     return 0;   }   