F1-别样的出题之旅（treasure）

（似乎要用文件输入输出）

	freopen("treasure.in", "r", stdin);
	freopen("treasure.out", "w", stdout);

题目背景

（Lsxszc $360$ 度环视四周）

Lsxszc：kkkw我想找你出一道F题！！！

kkkw：OK，我这里正好有一个藏宝图谜题，据说宝藏是一道非常不错的F题。

Lsxszc：哇！Lets go！

题目描述

藏宝图写着一个非常奇怪的谜题。

藏宝图上标记着一个 $n \times n$ 大小的表格，表格中填满了各式各样的小写字母，令坐标为 $(i,j)$ 的字母为 $x_{i,j}$。在探索解密的过程中，kkkw可以释放法术，随意修改表格中任意最多个格子中的字母，将其变为其他任意一个小写字母。当然，kkkw的法术也是有限制的，他最多可以修改 $k$ 个格子上的字母。至于Lsxszc，他可以呼吸。

想要得到藏宝图中的秘密，kkkw和Lsxszc需要首先从表格的左上角开始移动，最终移动到表格的右下角为止，每一步可以往右或往下移动一格。这样，从表格的左上角移动到右下角，就一共会经过 $2n - 1$ 个格子，而这 $2n - 1$ 个格子中的小写字母将组成一段神奇的文字。而最终秘密宝藏的隐藏地点，就是最多修改个字母后，字典序最小的这一段神奇文字所描述的地方。

现在，请你帮助kkkw和Lsxszc找到秘密宝藏被隐藏的地点。

输入格式

$n \ \ k$

$x_{1,1} \ \ \dots \ \ x_{1,n}$

$\dots$

$x_{n,1} \ \ \dots \ \ x_{n,n}$

输出格式

共一行，输出一个有小写字母组成的字符串，表示字典序最小的宝藏隐藏地点。

输入输出样例 #1

输入 #1

4 2
abcd
bcde
bcad
bcde

输出 #1

aaabcde

输入输出样例 #2

输入 #2

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

输出 #2

aaaaaaadudsnz

说明/提示

样例 1 解释

修改后为

4 2
abcd
acde
acad
bcde

数据规模与约定

• 对于 $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$。

后记

Lsxszc：哇！这就是宝藏了吧！

（打开宝箱）

不错的F题：鼠标滚轮向上

Lsxszc：？（看向kkkw）