CF2109F Penguin Steps

黑暗的智者 Mouf 和光明的勇者 Fouad 再次进入了网格王国。这次他们找到了出口，但出口被凶猛的怪物把守！他们必须徒手战斗，无法召唤怪物助阵！ Mouf 和 Fouad 站在一个 $n \times n$ 的网格上。每个单元格 $(i, j)$ 有一个数值 $a_{i,j}$ 和一个颜色。当 $c_{i,j} = 0$ 时单元格为白色，$c_{i,j} = 1$ 时为黑色。 Mouf 从左上角 $(1, 1)$ 出发，Fouad 从左下角 $(n, 1)$ 出发，两人都要前往出口单元格 $(r, n)$。 一条路径被定义为相邻单元格（共享水平或垂直边）的序列。路径的代价是该路径包含的所有单元格（包括起点和终点）中 $a_{i,j}$ 的最大值。 定义： - $\mathrm{dis}_M$ 表示 Mouf 从起点 $(1, 1)$ 到出口 $(r, n)$ 的所有有效路径中的最小可能代价； - $\mathrm{dis}_F$ 表示 Fouad 从起点 $(n, 1)$ 到出口 $(r, n)$ 的所有有效路径中的最小可能代价。 在移动前，Mouf 可以执行最多 $k$ 次操作。每次操作中，他可以选择任意黑色单元格并将其数值增加 $1$（可以多次选择同一单元格）。 Mouf 希望在确保自身代价 $\mathrm{dis}_M$ 不变（就像他没有执行任何操作时一样）的前提下，最大化 $\mathrm{dis}_F$。如果 Mouf 采取最优策略，$\mathrm{dis}_M$ 和 $\mathrm{dis}_F$ 的值将分别是多少？

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^3$）。接下来是测试用例描述。 每个测试用例的第一行包含三个整数 $n$、$r$ 和 $k$（$2 \le n \le 300$，$1 \le r \le n$，$0 \le k \le 10^6$）——分别表示网格边长、出口所在行号和允许的操作次数。 接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$（$1 \le a_{ij} \le 10^6$）——表示第 $i$ 行单元格的数值。 接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $c_i$——表示第 $i$ 行单元格的颜色（若 $c_{i,j}=\mathtt{0}$ 为白色，$c_{i,j} = \mathtt{1}$ 为黑色）。 保证所有测试用例的 $n^2$ 之和不超过 $9 \cdot 10^4$。

对于每个测试用例，输出两个整数——表示 Mouf 采取最优策略后的 $\mathrm{dis}_M$ 和 $\mathrm{dis}_F$。

**第一个测试用例解释：** - 虽然 Mouf 可以执行最多 $30$ 次操作，但他无法将 $\mathrm{dis}_F$ 提高到超过 $2$；他只能对 $(2,2)$ 进行操作，因为对 $(1,1)$ 或 $(1,2)$ 操作会改变 $\mathrm{dis}_M$。 - Mouf 可以对 $(2,2)$ 执行全部 $30$ 次操作，但 Fouad 仍可以走路径 $(2,1) \rightarrow (1,1) \rightarrow (1,2)$，其代价为 $2$。 **第二个测试用例解释：** Mouf 可以对 $(2,2)$ 执行 $2$ 次操作，对 $(3,2)$ 执行 $3$ 次操作。可以证明 $\mathrm{dis}_F$ 无法超过 $5$。 翻译由 DeepSeek V3 完成