Scaygerboss

题意翻译

有 $a+b+1$ 个会动的棋子，在一个大小为 $n\times m$ 的棋盘上，棋盘上有一些点有障碍。棋子中，有 $a$ 个红色棋子，$b$ 个蓝色棋子，和 $1$ 个既能当作红棋子又能当作蓝棋子的通配棋子。 一个局面是好的，当且仅当对于每个格子，要么这个格子上没有棋子，要么这个格子上恰好存在一个红棋子与一个蓝棋子。 每个棋子有自己的初始位置 $(x_i,y_i)$ 和速度 $t_i$，其中 $t_i$ 表示自己走到相邻的格子所需要的时间。 你可以控制所有棋子的移动。请问最少多少时间后能达到处于一个好的局面。

题目描述

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<=10^{9} $ ): 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.

输出格式

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

输入输出样例

输入样例 #1

4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2

输出样例 #1

2

输入样例 #2

2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2

输出样例 #2

-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.