H. Самая безбашенная оборона
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в очень популярную игру в жанре Tower Defense «Runnerfield 2». В ней игрок выставляет защитные башни, которые атакуют врагов, идущих от некоторой начальной точки до базы игрока.

Вам дано клетчатое поле размера $$$n \times m$$$, на котором уже расставлены $$$k$$$ башен и проложен маршрут, через который будут идти враги. Клетка на пересечении $$$x$$$-й строки и $$$y$$$-го столбца обозначается как $$$(x, y)$$$.

Каждую секунду башня наносит $$$p_i$$$ единиц урона всем врагам в радиусе её действия. Например, если враг расположен в клетке $$$(x, y)$$$, а башня в $$$(x_i, y_i)$$$, и её радиус равен $$$r$$$, тогда врагу будет нанесён урон $$$p_i$$$, если $$$(x - x_i) ^ 2 + (y - y_i) ^ 2 \le r ^ 2$$$.

Враги идут из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$, посещая каждую клетку пути ровно один раз. Враг моментально перемещается на соседнюю по горизонтали или вертикали клетку, однако перед этим он проводит в текущей клетке одну секунду. Если в эту секунду его здоровье стало равно нулю или ниже нуля, то враг больше не может перемещаться. Игрок проигрывает, если враг смог добраться до клетки $$$(n, m)$$$ и может сделать ещё одно перемещение.

По умолчанию все башни обладают нулевым радиусом действия, но игрок может сделать радиус башни равным целому числу $$$r$$$ ($$$r > 0$$$) за это здоровье всех врагов увеличится на $$$3^r$$$, однако каждое $$$r$$$ может быть использовано не более чем для одной башни.

Допустим, враг имел $$$h$$$ единиц базового здоровья. Если радиусы башен $$$2$$$, $$$4$$$ и $$$5$$$, то его здоровье в начале пути будет $$$h + 3 ^ 2 + 3 ^ 4 + 3 ^ 5 = h + 9 + 81 + 243 = h + 333$$$. Выбор радиусов происходит один раз до появления врагов и не может быть изменён после начала игры.

Найдите максимальное количество базового здоровья $$$h$$$, при котором возможно установить радиусы так, чтобы игрок не проиграл при прохождении врага со здоровьем $$$h$$$ (без учёта прибавок за радиусы башен).

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

В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 50, 1 \le k < n \cdot m$$$) — размеры поля и количество башен на нём.

В следующих $$$n$$$ строках даётся по $$$m$$$ символов — описание очередной строки поля, где символ «.» обозначает пустую клетку, символ «#» клетку пути, по которой пройдут враги.

Далее следует $$$k$$$ строк — описание башен. Каждая строка описания содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$p_i$$$ ($$$1 \le x_i \le n, 1 \le y_i \le m, 1 \le p_i \le 500$$$) — координаты башни и её параметр атаки. Все координаты соответствуют пустым клеткам на игровом поле, а так же все пары $$$(x_i, y_i)$$$ попарно различны.

Гарантируется, что сумма $$$n \cdot m$$$ не превосходит $$$2500$$$ по всем тестовым случаям.

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

Для каждого набора входных данных в отдельной строке выведите максимальное количество базового здоровья $$$h$$$, при котором возможно установить радиусы так, чтобы игрок не проиграл при прохождении врага со здоровьем $$$h$$$ (без учёта прибавок за радиусы башен).

Если невозможно выбрать радиусы даже для врага с $$$1$$$ единицей базового здоровья, выведите «0».

Пример
Входные данные
6
2 2 1
#.
##
1 2 1
2 2 1
#.
##
1 2 2
2 2 1
#.
##
1 2 500
3 3 2
#..
##.
.##
1 2 4
3 1 3
3 5 2
#.###
#.#.#
###.#
2 2 2
2 4 2
5 5 4
#....
#....
#....
#....
#####
3 2 142
4 5 9
2 5 79
1 3 50
Выходные данные
0
1
1491
11
8
1797
Примечание

В первом примере нет смысла увеличивать радиус башни, так как она не сможет нанести достаточное количество урона монстру даже с $$$1$$$ единицей здоровья.

Во втором примере радиус башни равен $$$1$$$, она наносит урон монстру в клетках $$$(1, 1)$$$ и $$$(2, 2)$$$.

В третьем примере радиус башни равен $$$2$$$, она наносит урон монстру на всех клетках пути. Если базовое здоровье врага $$$1491$$$, то после прибавки за радиус башни его здоровье будет $$$1491 + 3 ^ 2 = 1500$$$, что в точности будет равно урону, который ему нанесёт башня за три секунды.

В четвёртом примере у башни $$$(1, 2)$$$ радиус $$$1$$$, а у башни $$$(3, 1)$$$ радиус $$$2$$$.