Вы играете в очень популярную игру в жанре 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\) (без учёта прибавок за радиусы башен).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите максимальное количество базового здоровья \(h\), при котором возможно установить радиусы так, чтобы игрок не проиграл при прохождении врага со здоровьем \(h\) (без учёта прибавок за радиусы башен).
Если невозможно выбрать радиусы даже для врага с \(1\) единицей базового здоровья, выведите «0».
Примечание
В первом примере нет смысла увеличивать радиус башни, так как она не сможет нанести достаточное количество урона монстру даже с \(1\) единицей здоровья.
Во втором примере радиус башни равен \(1\), она наносит урон монстру в клетках \((1, 1)\) и \((2, 2)\).
В третьем примере радиус башни равен \(2\), она наносит урон монстру на всех клетках пути. Если базовое здоровье врага \(1491\), то после прибавки за радиус башни его здоровье будет \(1491 + 3 ^ 2 = 1500\), что в точности будет равно урону, который ему нанесёт башня за три секунды.
В четвёртом примере у башни \((1, 2)\) радиус \(1\), а у башни \((3, 1)\) радиус \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|