CF1031D.Minimum path

You are given a matrix of size $n \times n$ filled with lowercase English letters. You can change no more than $k$ letters in this matrix.

Consider all paths from the upper left corner to the lower right corner that move from a cell to its neighboring cell to the right or down. Each path is associated with the string that is formed by all the letters in the cells the path visits. Thus, the length of each string is $2n - 1$.

Find the lexicographically smallest string that can be associated with a path after changing letters in at most $k$ cells of the matrix.

A string $a$ is lexicographically smaller than a string $b$, if the first different letter in $a$ and $b$ is smaller in $a$.

你将得到一个大小为 $n \times n$ 的矩阵，其中填充有小写英文字母。你可以对该矩阵中至多 $k$ 个字母进行修改。

考虑所有从左上角到右下角的路径，每一步只能向右或向下移动到相邻格子。每条路径对应一个字符串，该字符串由路径所经过的所有格子中的字母按顺序拼接而成。因此，每个字符串的长度均为 $2n - 1$。

在最多修改矩阵中 $k$ 个格子的字母后，求所有可能路径所对应字符串中字典序最小的一个。

字符串 $a$ 字典序小于字符串 $b$，当且仅当 $a$ 与 $b$ 在第一个不同的位置上，$a$ 中的字母更小。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2000$, $0 \le k \le n^2$) — the size of the matrix and the number of letters you can change.

Each of the next $n$ lines contains a string of $n$ lowercase English letters denoting one row of the matrix.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2000$，$0 \le k \le n^2$）—— 分别表示矩阵的大小以及你可以修改的字母数量。

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

Output the lexicographically smallest string that can be associated with some valid path after changing no more than $k$ letters in the matrix.

输出在矩阵中最多更改 $k$ 个字母后，与某条有效路径相对应的字典序最小的字符串。

In the first sample test case it is possible to change letters 'b' in cells $(2, 1)$ and $(3, 1)$ to 'a', then the minimum path contains cells $(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)$. The first coordinate corresponds to the row and the second coordinate corresponds to the column.

在第一个样例测试用例中，可以将位于单元格 $(2, 1)$ 和 $(3, 1)$ 的字母 'b' 改为 'a'，此时最短路径包含单元格 $(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)$。其中第一个坐标表示行号，第二个坐标表示列号。