Convenience Zone

Hyeonseong, worn out from a 4-hour round trip commute, is looking for a room to rent. He only cares about the monthly rent and the distance to the nearest convenience store.

He gives every room on the map a convenience zone score and picks the room with the lowest score. The score is calculated as follows.

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

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

Hyeonseong chose the room with the lowest convenience zone score. What is that score?

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

From the second line, the next $R$ lines each contain three integers $a_i$, $b_i$, $p_i$ separated by spaces. This means the $i$-th room is at $(a_i, b_i)$ and its monthly rent is $p_i$.

From line $R+2$, the next $C$ lines each contain two integers $c_j$ and $d_j$ separated by a space. This means the $j$-th convenience store is at $(c_j, d_j)$.

All rooms and convenience stores are at different positions. In other words, each position holds at most one room or one convenience store.

Print the convenience zone score of the room Hyeonseong chose, on the first line.

• $2 \le N \le 1{,}000$
• $2 \le M \le 1{,}000$
• $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 100$
• There is at least one room and at least one convenience store.

In the first example, the room with rent 3 and a convenience store 2 steps away has the lowest score, 6.

In the second example, the room with rent 2 and a convenience store 2 steps away has the lowest score, 4.