给定一个大小为 $$$n \times n$$$ 的矩阵,其中填充有小写英文字母。您最多可以更改此矩阵中的 $$$k$$$ 个字母。
考虑从左上角到右下角从一个单元向右或向下移动到其相邻单元的所有路径。每条路径都与由该路径访问的单元格中的所有字母组成的字符串相关联。因此,每个字符串的长度为 $$$2n - 1$$$。
在更改矩阵的最多 $$$k$$$ 单元格中的字母后,找到可与路径关联的字典顺序最小的字符串。
如果 $$$a$$$ 和 $$$b$$$ 中的第一个不同字母在 $$$a$$$ 中较小,则字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2000$$$, $$$0 \le k \le n^2$$$) — 矩阵的大小和可以更改的字母数量。
接下来的 $$$n$$$ 行包含一串 $$$n$$$ 小写英文字母,表示矩阵的一行。
输出
在更改矩阵中不超过 $$$k$$$ 个字母后,输出可与某些有效路径关联的字典顺序最小的字符串。
示例
输入 #1
4 2 abcd bcde bcad bcde
输出 #1
aaabcde
输入 #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)$$$。第一个坐标对应于行,第二个坐标对应于列。