Xiao Ming's father bought him a box of toy soldiers, including $K$ infantrymen, $K$ cavalrymen, and one celestial soldier, all tall, mighty, and realistic. The box also contains an $M \times N$ chessboard, where each cell $(i, j)$ has a height $H_{ij}$ and is large enough to hold all the toy soldiers. Xiao Ming placed all the toy soldiers on the chessboard and suddenly thought of an interesting game: choose $T$ distinct cells and assign an importance value $R_i$ to each chosen cell $i$. The goal of the game is to move a toy soldier to an adjacent cell (up, down, left, or right, without moving off the board) in each step, such that eventually, each chosen cell $i$ contains exactly $R_i$ toy soldiers. Xiao Ming wants all toy soldiers to be in one of the selected cells, so he always ensures that the sum of the importance values of the $T$ selected cells equals the total number of toy soldiers. To increase the difficulty, Xiao Ming set some rules for the movement of the toy soldiers:

• Infantrymen can only climb to higher ground. Therefore, if two cells $A$ and $B$ are adjacent, an infantryman can move from $A$ to $B$ if and only if the height of $A$ is less than or equal to the height of $B$.
• Cavalrymen can only jump to lower ground. Therefore, if two cells $A$ and $B$ are adjacent, a cavalryman 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 celestial soldier is technically versatile and its movement is not restricted in any way.

However, after playing a few times, Xiao Ming found the game too difficult and often could not reach his goal after a long time. Thus, he designed a "superpower." Each time the superpower is used, although it cannot move any toy soldier, it allows for any number of swap operations, where each swap exchanges the positions of two toy soldiers. After the superpower is used, the toy soldiers can continue to move as usual. With the help of this powerful superpower, the game is easy to complete, but how can the number of times the superpower is used be minimized?

Input

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 of $(x_i, y_i)$, representing the initial positions of each toy soldier. The first $K$ represent infantrymen, the next $K$ represent cavalrymen, and the last one represents the celestial soldier.

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

The following $M$ lines each contain $N$ integers. The $j$-th number in the $i$-th line is the height of the cell $H_{ij}$. The heights are positive integers not exceeding $100$. Note: Different toy soldiers may have the same initial position. The input data is guaranteed to be correct, and the sum of the importance values of the $T$ selected cells is guaranteed to be equal to $2K+1$.

Output

Output a single line containing the minimum number of times the superpower is used.

Examples

Input 1

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

Output 1

1