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