F. Шаги пингвина
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Моуф, хитрый мастер Тьмы, и Фуад, смелый чемпион Света, снова вошли в Царство Сетки. На этот раз они нашли выход, но он охраняется свирепыми монстрами! Им придется сражаться голыми руками вместо того, чтобы призывать монстров!

Моуф и Фуад стоят на сетке размером $$$n \times n$$$. Каждая ячейка $$$(i, j)$$$ имеет значение $$$a_{i,j}$$$ и цвет. Цвет ячейки белый, если $$$c_{i,j} = 0$$$, и черный, если $$$c_{i,j} = 1$$$.

Моуф начинает в верхнем левом углу $$$(1, 1)$$$, а Фуад начинает в нижнем левом углу $$$(n, 1)$$$. Оба пытаются добраться до выходной ячейки $$$(r, n)$$$.

Путь определяется как последовательность смежных ячеек (имеющих общую горизонтальную или вертикальную грань). Стоимость пути — это максимальное значение $$$a_{i, j}$$$ среди всех ячеек, включенных в путь (включая первую и последнюю ячейки).

Обозначим:

  • $$$\mathrm{dis}_M$$$ — минимально возможная стоимость допустимого пути от начальной позиции Моуфа $$$(1, 1)$$$ до выхода $$$(r, n)$$$;
  • $$$\mathrm{dis}_F$$$ — минимально возможная стоимость допустимого пути от начальной позиции Фуада $$$(n, 1)$$$ до выхода $$$(r, n)$$$.

Перед движением Моуф может выполнить не более $$$k$$$ операций. На каждой операции он может выбрать любую черную ячейку и увеличить ее значение на $$$1$$$ (возможно, выбирая одну и ту же ячейку несколько раз).

Моуф хочет максимизировать $$$\mathrm{dis}_F$$$, при этом обеспечивая, чтобы его собственная стоимость $$$\mathrm{dis}_M$$$ оставалась неизменной (как будто он не выполнял никаких операций). Если Моуф действует оптимально, каковы значения $$$\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$$$) — сторона сетки, номер строки выходной ячейки и количество разрешенных операций.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$1 \le a_{ij} \le 10^6$$$) — значения ячеек в $$$i$$$-й строке.

$$$i$$$-я из следующих $$$n$$$ строк содержит бинарную строку $$$c_i$$$ длины $$$n$$$, обозначающую цвета ячеек в $$$i$$$-й строке (ячейка $$$(i,j)$$$ белая, если $$$c_{i,j}=\mathtt{0}$$$, и черная, если $$$c_{i,j} = \mathtt{1}$$$).

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превосходит $$$9 \cdot 10^4$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа — $$$\mathrm{dis}_M$$$ и $$$\mathrm{dis}_F$$$, если Моуф выполняет операции оптимально.

Примеры
Входные данные
4
2 1 30
2 2
1 1
11
01
3 3 5
9 2 2
2 3 2
2 2 2
111
111
010
7 3 12
3 3 3 3 5 1 1
9 4 8 3 3 5 5
9 4 8 7 3 3 3
4 4 4 4 9 4 9
4 4 4 4 9 4 9
1 4 4 4 4 4 9
1 1 4 4 9 9 9
1111111
1011111
1011111
1111111
1111101
1110001
0111111
5 3 1419
1219 678 1672 1858 1210
535 732 1316 345 296
1106 3060 507 216 1943
194 2124 47 87 4818
1007 329 1425 284 660
00010
10111
00101
10001
10100
Выходные данные
2 2
9 5
3 8
1943 2426
Входные данные
1
8 2 2216
429 589 675 2022 259 452 733 967
1097 2880 256 1894 259 1052 345 692
911 831 513 1243 200 14 854 217
611 882 681 279 54 719 1469 1885
504 2524 1332 17 3113 34 1281 717
498 1896 1800 2231 731 364 69 1247
1397 399 68 448 1337 1076 166 3786
16 857 91 475 106 102 1517 1949
01010100
00101100
00001000
10100110
00001000
00100000
01100011
00001000
Выходные данные
733 1671
Примечание

В первом наборе входных данных:

  • Хотя Моуф может выполнить до $$$30$$$ операций, он не может увеличить $$$\mathrm{dis}_F$$$ более чем до $$$2$$$; он ограничен в применении операций только на $$$(2,2)$$$, потому что выполнение операций на $$$(1,1)$$$ или $$$(1,2)$$$ изменит $$$\mathrm{dis}_M$$$.
  • Моуф может применить все $$$30$$$ операций к ячейке $$$(2,2)$$$; однако Фуад все равно может следовать по пути $$$(2,1) \rightarrow (1,1) \rightarrow (1,2)$$$ со стоимостью $$$2$$$.

Во втором наборе входных данных Моуф может применить две операции на $$$(2,2)$$$ и три операции на $$$(3,2)$$$. Можно показать, что Моуф не может увеличить $$$\mathrm{dis}_F$$$ более чем до $$$5$$$.