有一个由小写英文字母组成的大小为 n×n 的矩阵。此矩阵中最多可以更改 k 个字母。

考虑从左上角到右下角的所有路径，从单元格到相邻的单元格向右或向下移动。

每个路径都与由路径访问的单元格中的所有字母组成的字符串。

因此，每个字符串的长度为 2n−1.

在矩阵的最多 k 个单元格中更改字母后，查找可与路径关联的最小字符串。

如果a 和 b 中的第一个不同字母在 a中较小，则字符串a 在词典序上比字符串 b 小。

第一行包含两个整数 n 和 k（1≤n≤2000, 0≤k≤n²）矩阵的大小和可以更改的字母数。

接下来的 n 行中的每一行都包含一个由 n 个小写英文字母组成的字符串，表示矩阵的一行。

在矩阵中更改不超过 k 个字母后，输出可与某个有效路径关联的最小字符串

样例2输入

5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw

样例2输出

aaaepfafw

样例3输入

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

样例3输出

aaaaaaadudsnz

注释：

在第一个例子中，可以将单元（2,1）和（3,1）中的字母“b”更改为“a”，

然后最小路径包含单元（1,1）、（2,1）、（3,1）、（4,1）、（4,2）、（4,3）、（4,4）。

第一个坐标对应于行，第二个坐标对应于列。

张皓玚2021