편세권

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