题目

#include <bits/stdc++.h>
#define int long long
//#define int __int128

#define In(x) freopen(x ".in", "r", stdin)
#define Out(x) freopen(x ".out", "w", stdout)
#define File(x) (In(x), Out(x))

typedef long long LL;
typedef long long ll;
typedef unsigned long long ULL;
typedef std::pair<int, int> PII;

#define all(x) x.begin(),x.end()
#define mem(f, x) memset(f, x, sizeof(f))

#define kl k << 1
#define kr k << 1 | 1

#define pc(x) putchar(x)
#define endl '\n'

#define print(x) cerr << #x << '=' << x << endl
#define line cerr << "\n---------------------------------------------------------\n"
//#define cout cerr

const int INF = 4557430888798830399;
const double eps = 1e-8;

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int Min(int a, int b, int c) { return std::min(a, std::min(b, c)); }
int Max(int a, int b, int c) { return std::max(a, std::max(b, c)); }
int lowbit(int x) { return x & -x ; }

namespace fast_IO{
    template < typename T >
    inline void read(T &x){
        bool f = 1;
        x = 0;
        char ch = getchar();
        while ( ch < '0' || ch > '9' ) {
            if(ch == '-') f =! f;
            ch = getchar();
        }
        while ( ch >= '0' && ch <= '9' ) {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = getchar();
        }
        x = (f ? x : -x);
    }
    template < typename T, typename... Args >
    inline void read(T& x, Args&...x_) {
        read(x);
        read(x_...);
    }

    template < typename T >
    inline void write(T x, bool f) {
        if (x < 0)
            x = -x, putchar('-');
        static short Stack[50], top(0);
        do
            Stack[++top] = x % 10, x /= 10;
        while (x);
        while (top) putchar(Stack[top--] | 48);
        f ? putchar('\n') : putchar(' ');
    }
}
using namespace std;
using namespace fast_IO;

/***************************************************************************************************************************/
/**                                                                                                                       **/
/***************************************************************************************************************************/

const int N = 2020;
int n,k;
char s[N][N];
int f[N][N];
PII g[N][N];


struct node{
    int x1,y1,x2,y2;

    bool operator <(const node &tmp) const{
        return tmp.x1 < x1 ||
              (tmp.x1 == x1 && tmp.y1 < tmp.y1) ||
              (tmp.x1 == x1 && tmp.y1 == tmp.y1 && tmp.x2 < x2) ||
              (tmp.x1 == x1 && tmp.y1 == tmp.y1 && tmp.x2 == x2 && tmp.y2 < y2) ;
    }
};

map<node,int> mp;
vector<PII> v;
void solve(){
    for(int i = 1;i < n * 2;i++)
        pc('a');
}

PII minn(int x1,int y1,int x2,int y2){

    if(x1 == x1 && y1 == y2) return make_pair(x1,y1);

    node tmp = {x1,y1,x2,y2};
    int T = mp[tmp];
    if(T > 0) {
        if(T == 1) return make_pair(x1,y1);
        return make_pair(x2,y2);
    }
    if(s[x1][y1] < s[x2][y2]){
        mp[tmp] = 1;
        return make_pair(x1,y1);
    }
    if(s[x1][y1] > s[x2][y2]){
        mp[tmp] = 2;
        return make_pair(x2,y2);
    }


    PII res = minn(g[x1][y1].first , g[x1][y1].second , g[x2][y2].first , g[x2][y2].second);

    if(res == g[x1][y1]) {
        mp[tmp] = 1;
        return make_pair(x1,y1);
    }

    mp[tmp] = 2;
    return make_pair(x2,y2);
}


void Go(int x,int y){
    pc(s[ g[x][y].first ][ g[x][y].second ]);
    PII tmp = {0,0};
    if(g[x][y] != tmp ) Go(g[x][y].first,g[x][y].second);
}

void Print(PII ans){
    for(int i = 1;i < ans.first + ans.second;i++){
        pc('a');
    }

    Go(ans.first,ans.second);
}
signed main(){
    read(n,k);
    for(int i = 1;i <= n;i++) scanf("%s",s[i] + 1);

    f[1][1] = (s[1][1] != 'a');
    for(int i = 2;i <= n;i++)
        f[1][i] = f[1][i-1] + (s[1][i] != 'a');

    for(int i = 2;i <= n;i++)
        f[i][1] = f[i-1][1] + (s[i][1] != 'a');

    for(int i = 2;i <= n;i++)
        for(int j = 2;j <= n;j++)
            f[i][j] = min(f[i-1][j] , f[i][j-1]) + (s[i][j] != 'a');

    if(f[n][n] <= k)
        return solve() ,0;


    g[n][n] = make_pair(0,0);

    for(int i = n - 1;i >= 1;i--)
        g[n][i] = make_pair(n,i+1);

    for(int i = n - 1;i >= 1;i--)
        g[i][n] = make_pair(i+1,n);

    for(int i = n - 1;i >= 1;i--){
        for(int j = n - 1;j >= 1;j--){
            g[i][j] = minn(i+1,j,i,j+1);
        }
    }


    //for(int i = 1;i <= n;i++){
    //    for(int j = 1;j <= n;j++){
   //         cout << "(" << g[i][j].first << " " << g[i][j].second <<")" << " " ;
    //    }cout << endl;
    //}


    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(f[i][j] == k)
                v.push_back(make_pair(i,j));

    PII ans;
    int al = -1;
    for(PII i : v){
        if(al == -1){
            ans = i;
            al = i.first + i.second;
        }else{
            if(i.first + i.second > al){
                ans = i;
                al = i.first + i.second;
            }else if(i.first + i.second == al){
                ans = minn(ans.first,ans.second,i.first,i.second);
            }
        }
    }


    Print(ans);

    return 0;
}