Description

Xiaoming’s father bought him a box of toy soldiers: $K$ infantry, $K$ cavalry, and one “heavenly soldier”. Each one is tall and lifelike. The box also contains an $M\times N$ chessboard. Each cell $(i,j)$ has a height $H_{i,j}$, and is large enough to hold any number of toy soldiers.

Xiaoming places all the toy soldiers on the board and comes up with an interesting game: randomly choose $T$ different cells, and assign each chosen cell $i$ an importance value $R_i$. The goal of the game is: each time, move one toy soldier by one step in one of the four directions (east, south, west, north) to an adjacent cell (but it cannot move outside the board), and finally make every chosen cell $i$ contain exactly $R_i$ toy soldiers.

Xiaoming wants all toy soldiers to end up in the selected cells, so he always makes the sum of the importance values of the chosen $T$ cells equal to the total number of toy soldiers.

To make it harder, Xiaoming adds some movement rules:

• Infantry only climb to higher places. Therefore, if two cells $A$ and $B$ are adjacent, an infantry soldier can move from $A$ to $B$ if and only if the height of $A$ is less than or equal to the height of $B$.

• Cavalry only jump to lower places. Therefore, if two cells $A$ and $B$ are adjacent, a cavalry soldier can move from $A$ to $B$ if and only if the height of $A$ is greater than or equal to the height of $B$.

• The heavenly soldier is versatile, and its movement has no restrictions.

After playing a few times, Xiaoming finds the game too difficult, and he often cannot reach the goal after a long time. So he designs a “superpower”: each time he uses the superpower, he cannot move any toy soldier, but he may perform any number of swap operations, and each swap exchanges two toy soldiers. After this use of the superpower ends, he can continue moving the toy soldiers normally.

With this powerful superpower, the game becomes doable, but how can he minimize the number of times the superpower is used?

Input Format

The first line contains four integers: $M,N,K,T (2\le M,N\le 100, 1\le K\le 50, 1\le T\le 2K+1)$.

The second line contains $2K+1$ pairs $(x_i,y_i)$, representing the initial positions of all toy soldiers. The first $K$ are infantry, the next $K$ are cavalry, and the last one is the heavenly soldier.

The third line contains $T$ triples $(x_i,y_i,r_i)$. The $i$-th triple gives the position and importance value of the $i$-th target cell.

The next $M$ lines each contain $N$ integers. The $j$-th number on the $i$-th line is the height $H_{i,j}$ of that cell. Heights are positive integers not exceeding $100$. Note that different toy soldiers may have the same initial position. The input is guaranteed to be valid, and the sum of the importance values of the selected $T$ cells is guaranteed to be $2K+1$.

Output Format

Output only one line: the minimum number of times the superpower must be used.

4 6 2 5
1 1 1 5 4 1 4 5 3 3
1 2 1 2 6 1 3 2 1 3 6 1 4 3 1
3 2 6 1 3 5
2 1 7 4 4 6
2 3 1 4 3 4
4 3 4 3 2 3

1

Hint

All Constraints are included in the input format.

Translated by ChatGPT 5