편세권

왕복 4시간 통학에 지친 현성이는 자취방을 구하려고 한다. 현성이가 방을 고르는 기준은 월세와 편의점까지의 거리뿐이다.

현성이는 지도 위의 모든 방에 편세권 점수를 매기고, 그중 점수가 가장 낮은 집을 고른다. 편세권 점수는 다음과 같이 계산한다.

편세권 점수 = (방에서 가장 가까운 편의점까지의 거리 × 월세)

지도는 $N \times M$ 크기의 격자이다. 지도의 $x$행 $y$열 칸의 위치는 $(x,y)$로 나타낸다. 방의 위치가 $(a,b)$, 편의점의 위치가 $(c,d)$일 때 방에서 편의점까지의 거리는 $|a-c|+|b-d|$이다.

현성이는 가장 낮은 편세권 점수를 가진 방을 골랐다. 이 방의 편세권 점수는 얼마인가?

첫 번째 줄에 지도의 크기를 나타내는 정수 $N$과 $M$, 방의 개수 $R$, 편의점의 개수 $C$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $R$개의 줄에 걸쳐 방의 정보를 나타내는 세 정수 $a_i$, $b_i$, $p_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 방이 $(a_i, b_i)$에 있으며, 월세가 $p_i$임을 나타낸다.

$R+2$번째 줄부터 $C$개의 줄에 걸쳐 편의점의 정보를 나타내는 두 정수 $c_j$, $d_j$가 공백으로 구분되어 주어진다. 이는 $j$번째 편의점이 $(c_j, d_j)$에 있음을 나타낸다.

모든 방과 편의점의 위치는 서로 다르다. 즉, 한 위치에는 최대 한 개의 방이나 한 개의 편의점만 있을 수 있다.

첫째 줄에 현성이가 고른 방의 편세권 점수를 출력한다.

• $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$
• 방과 편의점은 각각 1개 이상 존재한다.

예제 1번의 경우 월세가 $3$이고, 편의점까지의 거리가 $2$인 자취방의 편세권 점수가 $6$으로 가장 낮다.

예제 2번의 경우 월세가 $2$이고, 편의점까지의 거리가 $2$인 자취방의 편세권 점수가 $4$로 가장 낮다.