您正在玩一款非常流行的塔防游戏,名为“Runnerfield 2”。在这款游戏中,玩家设置防御塔来攻击从某个起点移动到玩家基地的敌人。
你会得到一个大小为 $$$n \times m$$$ 的网格,上面已经放置了 $$$k$$$ 塔,并布置了一条敌人可以移动的路径。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。
每一秒,一座塔都会对其范围内的所有敌人造成 $$$p_i$$$ 单位的伤害。例如,如果敌人位于单元格$$$(x, y)$$$,而塔位于$$$(x_i, y_i)$$$,范围为$$$r$$$,则如果$$$(x - x_i) ^ 2 + (y - y_i) ^ 2 \le r ^ 2$$$,则敌人将受到$$$p_i$$$的伤害。
敌人从单元格 $$$(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”。
示例
输入 #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
输出 #1
0 1 1491 11 8 1797
注意
在第一个例子中,增加塔的射程是没有意义的,因为即使有 $$$1$$$ 单位的生命值,它也无法对怪物造成足够的伤害。
在第二个示例中,塔的范围为 $$$1$$$,它对单元格 $$$(1, 1)$$$ 和 $$$(2, 2)$$$ 中的怪物造成伤害。
在第三个例子中,塔的范围为$$$2$$$,它对所有路径单元格中的怪物造成伤害。如果敌人的基础生命值为$$$1491$$$,那么加上塔范围后,其生命值为$$$1491 + 3 ^ 2 = 1500$$$,正好等于塔在三秒内对其造成的伤害。
在第四个示例中,$$$(1, 2)$$$ 处的塔的范围为 $$$1$$$,$$$(3, 1)$$$ 处的塔的范围为 $$$2$$$。