Convenience Store Zone

A student who commutes four hours a day round trip wants to find a room near a convenience store.

He chooses a room using only the monthly rent and the distance to the nearest convenience store. To find the room he likes most, he gives every room on the map a convenience score and picks the room with the lowest score. The score is calculated as follows.

Convenience score = (distance from the room to the nearest convenience store × monthly rent)

The map is a grid of $N \times M$ cells. The cell in row $x$ and column $y$ is written as $(x,y)$. When a room is at $(a, b)$ and a convenience store is at $(c, d)$, the distance between them is $|a-c|+|b-d|$.

What is the convenience score of the room he picked, the one with the lowest score?

The first line contains the map size $N$ and $M$, the number of rooms $R$, and the number of convenience stores $C$, separated by spaces.

The next $R$ lines each contain three integers $a_i$, $b_i$, $p_i$, separated by spaces. These mean that the $i$-th room is at $(a_i, b_i)$ and its monthly rent is $p_i$.

The next $C$ lines each contain two integers $c_j$, $d_j$, separated by spaces. These mean that the $j$-th convenience store is at $(c_j, d_j)$.

All rooms and convenience stores are at different positions. A cell holds at most one room or one convenience store.

Print the convenience score of the room he picked on the first line.

• $2 \le N \le 5\times10^5$
• $2 \le M \le 5\times10^5$
• $2 \le R+C \le \min(NM, 5\times10^5)$
• $1 \le a_i, c_j \le N$
• $1 \le b_i, d_j \le M$
• $1 \le p_i \le 10^5$
• There is at least one room and at least one convenience store.