F. Penguin Stepstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputMouf, the clever master of Darkness, and Fouad, the brave champion of Light, have entered the Grid Realm once more. This time, they have found the exit, but it is guarded by fierce monsters! They must fight with their bare hands instead of summoning monsters!Mouf and Fouad are standing on an $$$n \times n$$$ grid. Each cell $$$(i, j)$$$ has a value $$$a_{i,j}$$$ and a color. The color of a cell is white if $$$c_{i,j} = 0$$$ and black if $$$c_{i,j} = 1$$$.Mouf starts at the top-left corner $$$(1, 1)$$$, and Fouad starts at the bottom-left corner $$$(n, 1)$$$. Both are trying to reach the exit cell at $$$(r, n)$$$.A path is defined as a sequence of adjacent cells (sharing a horizontal or vertical edge). The cost of a path is the maximum value of $$$a_{i, j}$$$ among all cells included in the path (including the first and last cells).Let: $$$\mathrm{dis}_M$$$ denote the minimum possible cost of a valid path from Mouf's starting position $$$(1, 1)$$$ to the exit $$$(r, n)$$$; $$$\mathrm{dis}_F$$$ denote the minimum possible cost of a valid path from Fouad's starting position $$$(n, 1)$$$ to the exit $$$(r, n)$$$. Before moving, Mouf can perform up to $$$k$$$ operations. In each operation, he may select any black cell and increment its value by $$$1$$$ (possibly choosing the same cell multiple times).Mouf wants to maximize $$$\mathrm{dis}_F$$$ while ensuring that his own cost $$$\mathrm{dis}_M$$$ remains unchanged (as if he performed no operations). If Mouf acts optimally, what are the values of $$$\mathrm{dis}_M$$$ and $$$\mathrm{dis}_F$$$?InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows. The first line of each test case contains three integers $$$n$$$, $$$r$$$, and $$$k$$$ ($$$2 \le n \le 300$$$, $$$1 \le r \le n$$$, $$$0 \le k \le 10^6$$$) — the length of the grid, the row number of the exit cell, and the number of allowed operations.The $$$i$$$-th of the next $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$1 \le a_{ij} \le 10^6$$$) — the values of the cells in the $$$i$$$-th row.The $$$i$$$-th of the next $$$n$$$ lines contains a binary string $$$c_i$$$ of length $$$n$$$ — denoting the color of the cells in the $$$i$$$-th row (cell $$$(i,j)$$$ is white if $$$c_{i,j}=\mathtt{0}$$$ and black if $$$c_{i,j} = \mathtt{1}$$$).It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$9 \cdot 10^4$$$.OutputFor each test case, output two integers — $$$\mathrm{dis}_M$$$ and $$$\mathrm{dis}_F$$$ if Mouf performs the operations optimally.ExamplesInput42 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 6600001010111001011000110100Output2 2
9 5
3 8
1943 2426
Input18 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 19490101010000101100000010001010011000001000001000000110001100001000Output733 1671
NoteIn the first test case: Although Mouf can perform up to $$$30$$$ operations, he can not increase $$$\mathrm{dis}_F$$$ beyond $$$2$$$; he is restricted to applying operations only on $$$(2,2)$$$, because performing operations on $$$(1,1)$$$ or $$$(1,2)$$$ would change $$$\mathrm{dis}_M$$$. Mouf may apply all $$$30$$$ operations on cell $$$(2,2)$$$; however, Fouad can still follow the path $$$(2,1) \rightarrow (1,1) \rightarrow (1,2)$$$ with a cost of $$$2$$$. In the second test case, Mouf can apply two operations on $$$(2,2)$$$ and three operations on $$$(3,2)$$$. It can be shown that Mouf can not increase $$$\mathrm{dis}_F$$$ beyond $$$5$$$.