31850번 - 편세권 (Hard)

문제

왕복 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ドル$개 이상 존재한다.

힌트

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

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