聪明的黑暗大师穆夫和勇敢的光明冠军福阿德再次进入网格领域。这一次,他们找到了出口,但却被凶猛的怪物把守!他们必须徒手战斗,而不是召唤怪物!
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}_F$$$,同时确保自己的成本 $$$\mathrm{dis}_M$$$ 保持不变 不变 (就好像他没有执行任何操作)。如果 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}$$$ 则单元格 $$$(i,j)$$$ 为白色,如果 $$$c_{i,j}=\mathtt{0}$$$ 则为黑色$$$c_{i,j} = \mathtt{1}$$$)。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$9 \cdot 10^4$$$。
输出
对于每个测试用例,如果 Mouf 执行最佳操作,则输出两个整数 - $$$\mathrm{dis}_M$$$ 和 $$$\mathrm{dis}_F$$$。
示例
输入复制
42 1 302 21 111013 3 59 2 22 3 22 2 21111110107 3 123 3 3 3 5 1 19 4 8 3 3 5 59 4 8 7 3 3 34 4 4 4 9 4 94 4 4 4 9 4 91 4 4 4 4 4 91 1 4 4 9 9 911111111011111101111111111111111101111000101111115 3 14191219 678 1672 1858 1210535 732 1316 345 2961106 3060 507 216 1943194 2124 47 87 48181007 329 1425 284 6600001010111001011000110100
输出复制
2 2 9 5 3 8 1943 2426
输入复制
18 2 2216429 589 675 2022 259 452 733 9671097 2880 256 1894 259 1052 345 692911 831 513 1243 200 14 854 217611 882 681 279 54 719 1469 1885504 2524 1332 17 3113 34 1281 717498 1896 1800 2231 731 364 69 12471397 399 68 448 1337 1076 166 378616 857 91 475 106 102 1517 19490101010000101100000010001010011000001000001000000110001100001000
输出复制
733 1671
注意
在第一个测试用例中:
- 虽然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)$$$ 应用两个操作,对 $$$(3,2)$$$ 应用三个操作。可以证明 Mouf 不能将 $$$\mathrm{dis}_F$$$ 增加到超过 $$$5$$$。