Guardian Protection

In this problem, you are given a grid representing a forest where each cell is either free ('.') or blocked ('#'). There are two types of characters in the forest: Marauders and Guardians. Each character is initially located at a specific cell and is associated with a movement cost per step. A Guardian can protect a Marauder if it can reach any cell whose Manhattan distance from the Marauder is at most (p). The task is to determine the minimum time required so that every Marauder is within the protection range of at least one Guardian. If it is impossible to protect all Marauders, output -1. In the special case where there are no Marauders, output 0.


Note: The movement of any Guardian follows a cost pattern. Specifically, if a Guardian has an associated cost (t), then moving from one cell to an adjacent cell (up, down, left, right) costs (t). The forest may contain obstacles that block movement. The final answer is the maximal minimal time taken among all Marauders ensuring at least one Guardian can protect them.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns in the forest grid.
2. The second line contains two integers \(M\) and \(G\) representing the number of Marauders and Guardians respectively.
3. Next, there are \(n\) lines each containing a string of length \(m\) describing the forest. A character '.' denotes a free cell and '#' denotes an obstacle.
4. The following line contains an integer \(p\), the protection range of each Guardian.
5. Then, there are \(M\) lines. Each line contains three integers \(r\), \(c\), and \(t\) describing the row, column, and movement cost of a Marauder.
6. Finally, there are \(G\) lines. Each line contains three integers \(r\), \(c\), and \(t\) describing the initial row, column, and movement cost of a Guardian.

All indices are 0-based.

outputFormat

The output is a single integer printed to stdout representing the minimum time required to ensure every Marauder is within the protection range of at least one Guardian. If it is impossible to protect all Marauders, output -1. If there are no Marauders, output 0.

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

2