CF2109F Penguin Steps

Mouf, 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 $ ?

Each 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 $ .

For each test case, output two integers — $ \mathrm{dis}_M $ and $ \mathrm{dis}_F $ if Mouf performs the operations optimally.

In 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 $ .