CF513F2.Scaygerboss

Cthulhu decided to catch Scaygerboss. Scaygerboss found it out and is trying to hide in a pack of his scaygers. Each scayger except Scaygerboss is either a male or a female. Scaygerboss's gender is "other".

Scaygers are scattered on a two-dimensional map divided into cells. A scayger looks nerdy and loveable if it is staying in the same cell with exactly one scayger of a gender that is different from its own gender. Cthulhu will not be able to catch Scaygerboss if all the scaygers on the map look nerdy and loveable.

The scaygers can move around at different speeds. For each scayger, we are given the time it takes this scayger to move from a cell to an adjacent cell. Cells are adjacent if they share a common side. At any point of time, each cell that does not contain an obstacle can be occupied by an arbitrary number of scaygers. Scaygers cannot move to cells with obstacles.

Calculate minimal time in order to make all scaygers look nerdy and loveable if they move optimally toward this goal.

克苏鲁决定抓捕斯凯格博斯。斯凯格博斯得知此事后，正试图躲藏在一群斯凯格之中。除斯凯格博斯外，每个斯凯格要么是雄性，要么是雌性；而斯凯格博斯的性别为“其他”。

斯凯格们散布在一张划分为若干单元格的二维地图上。当一个斯凯格所在单元格中恰好存在一个与其自身性别不同的斯凯格时，该斯凯格便显得呆萌又可爱。若地图上所有斯凯格均显得呆萌又可爱，则克苏鲁将无法抓捕斯凯格博斯。

斯凯格们可按不同速度移动。对每个斯凯格，我们已知其从一个单元格移动至相邻单元格所需的时间。两个单元格相邻当且仅当它们有一条公共边。在任意时刻，不含障碍物的单元格可容纳任意数量的斯凯格。斯凯格不可移入含障碍物的单元格。

请计算在斯凯格们为达成“所有斯凯格均显得呆萌又可爱”这一目标而进行最优移动的前提下，所需的最短时间。

The first line contains 4 integers: n, m, males, females (0 ≤ males, females ≤ n·m). n and m are dimensions of the map; males and females are numbers of male scaygers and female scaygers.

Next n lines describe the map. Each of these lines contains m characters. Character '.' stands for a free cell; character '#' stands for a cell with an obstacle.

The next line contains 3 integers r, c, and t (1 ≤ r ≤ n, 1 ≤ c ≤ m, 1 ≤ t ≤ 109): the current coordinates of Scaygerboss and the time it takes Scaygerboss to move to an adjacent cell. The next males lines contain coordinates and times of male scaygers in the same format as for Scaygerboss. The next females lines contain coordinates and times of female scaygers in the same format as for Scaygerboss. (The coordinates and times adhere to the same limits as for Scaygerboss.) All scaygers reside in cells without obstacles.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem F1 (14 points), the constraints 1 ≤ n, m ≤ 11 will hold.
• In subproblem F2 (6 points), the constraints 1 ≤ n, m ≤ 22 will hold.

第一行包含 4 个整数：$n$、$m$、$males$、$females$（$0 \le males,\,females \le n \cdot m$）。其中 $n$ 和 $m$ 是地图的尺寸；$males$ 和 $females$ 分别表示雄性 Scayger 和雌性 Scayger 的数量。

接下来的 $n$ 行描述地图。每行包含 $m$ 个字符。字符 . 表示空闲格子；字符 # 表示障碍物格子。

下一行包含 3 个整数 $r$、$c$ 和 $t$（$1 \le r \le n$，$1 \le c \le m$，$1 \le t \le 10^9$）：分别表示 Scaygerboss 当前所在的坐标（行号 $r$、列号 $c$）以及 Scaygerboss 移动到相邻格子所需的时间。随后的 $males$ 行以与 Scaygerboss 相同的格式给出各雄性 Scayger 的坐标和移动时间。再之后的 $females$ 行以与 Scaygerboss 相同的格式给出各雌性 Scayger 的坐标和移动时间。（这些坐标与时间均满足与 Scaygerboss 相同的取值范围限制。）所有 Scayger 均位于无障碍物的格子中。

本题包含两个子问题。两个子问题对输入数据有不同的约束条件。正确提交任一子问题可获得相应分数。子问题描述如下：

• 子问题 F1（14 分）：约束条件为 $1 \le n,\,m \le 11$。
• 子问题 F2（6 分）：约束条件为 $1 \le n,\,m \le 22$。

Output the minimum possible time it takes to make all scaygers look nerdy and loveable or -1 if it is impossible.

输出使所有 Scayger 变得呆萌又可爱所需的最短时间；如果无法实现，则输出 -1。

Consider the first sample test. The scaygers are hiding on a 4 by 4 map. Scaygerboss initially resides in the cell (2, 1) and can move between cells in 1 unit of time. There are also 2 male and 3 female scaygers on the map. One of the females initially is in the cell (1, 1), and all the other scaygers are in the cell (2, 1). All the scaygers move between cells in 2 units of time. If Scaygerboss and the female scayger from the cell (1, 1) move to the cell (1, 2), and a male and a female scayger from those residing in the cell (2, 1) move to the cell (1, 1), then all the scaygers will look nerdy and lovable in 2 units of time.

考虑第一个样例测试。怪兽们隐藏在一个 $4 \times 4$ 的地图上。怪兽首领初始位于单元格 $(2,\,1)$，且可在 $1$ 单位时间内在单元格之间移动。地图上还有 $2$ 只雄性怪兽和 $3$ 只雌性怪兽。其中一只雌性怪兽初始位于单元格 $(1,\,1)$，其余所有怪兽均位于单元格 $(2,\,1)$。所有怪兽均需 $2$ 单位时间在单元格之间移动。若怪兽首领与位于 $(1,\,1)$ 的那只雌性怪兽一同移至单元格 $(1,\,2)$，同时一只雄性怪兽与一只雌性怪兽（均来自位于 $(2,\,1)$ 的怪兽群）移至单元格 $(1,\,1)$，则所有怪兽将在 $2$ 单位时间内显得呆萌又可爱。