4294: T4 寻宝（treasure）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## T4 寻宝（treasure）
### 题目描述
小明意外的获得了一张神奇的藏宝图，但想要获得藏宝图中隐藏着的秘密宝藏的地址，就需要解开藏宝图中所隐藏的秘密。
藏宝图上标记着一个 $n \times n$ 大小的表格，表格中填满了各式各样的小写字母，在探索解密的过程中，小明可以释放法术，随意修改表格中任意最多个格子中的字母，将其变为其他任意一个小写字母。当然，小明的法术也是有限制的，他最多可以修改 $k$ 个格子上的字母。
想要得到藏宝图中的秘密，小明需要首先从表格的左上角开始移动，最终移动到表格的右下角为止，每一步可以往右或往下移动一格。这样，从表格的左上角移动到右下角，就一共会经过 $2n - 1$ 个格子，而这 $2n - 1$ 个格子中的小写字母将组成一段神奇的文字。而最终秘密宝藏的隐藏地点，就是最多修改个字母后，字典序最小的这一段神奇文字所描述的地方。
现在，请你帮助小明找到秘密宝藏被隐藏的地点。
输入
### 输入格式
第一行输入两个数字 $n,k$，表示藏宝图上表格的大小和最多可以修改的格子数量。
接下来，输入一个由小写字母组成的 $n$ 行 $n$ 列的表格，表示解密需要的表格。
输出
### 输出格式
共一行，输出一个有小写字母组成的字符串，表示字典序最小的宝藏隐藏地点。
样例输入 复制
4 2
abcd
bcde
bcad
bcde样例输出 复制
aaabcde提示
### 样例 1 输入
```
4 2
abcd
bcde
bcad
bcde
```
### 样例 1 输出
```
aaabcde
```
### 样例 1 解释
修改后为
```
4 2
abcd
acde
acad
bcde
```
先向下后向右。
### 样例 2 输入
```
7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz
```
### 样例 2 输出
```
aaaaaaadudsnz
```
### 数据规模与约定
- 对于 $30\%$ 的数据，保证 $n \le 5,k\le 2$。
- 对于 $50\%$ 的数据，保证 $n \le 5$。
- 对于另 $20\%$ 的数据，保证 $k = 0$。
- 对于 $100\%$ 的数据，保证 $1 \le n \le 1000, 0 \le k \le n^2$。