[고등부] 2022 KOI 2차대회 대비 모의고사 (6월 3주차)

한강에서 조업하는 어선의 소유자는 여름 시즌에 사업을 최적화하기로 결정했습니다.

그는 낚시를 하기 위한 시즌 허가를 받았습니다.

n개의 포인트에서 낚시를 할 수 있으며, 각 포인트는 항구로부터 x_1, x_2, ..., x_n 킬로미터 떨어져 있습니다.

i번째 포인트에서는 최대 a_i톤의 물고기를 잡을 수 있습니다.

또한, 잡은 물고기를 m개의 포인트에서 판매할 수 있습니다.

각 포인트는 항구로부터 y_1, y_2, ... , y_m 킬로미터 떨어져 있습니다.

j번째 포인트에서는 최대 b_j톤의 물고기를, 톤당 c_j원에 팔 수 있습니다.

배는 물고기를 잡다가 시즌이 끝나면 항구로 돌아와야 합니다.

시즌 동안 배는 마음대로 강 위아래로 이동하여 물고기를 잡거나 팔기 위해 멈출 수 있습니다.

선박의 운반 능력은 잡은 물고기의 양을 운반하기에 충분합니다.

항구에서 멀어지면 선박은 물길을 거슬러 이동하여 연료를 킬로미터당 p원 소모합니다.

항구 쪽으로 이동할 때는 선박은 물길을 타고 이동하기 때문에 연료를 소비하지 않습니다.

시즌이 끝나면 이익은 판매된 물고기의 총 비용에서 사용된 총 연료 비용을 뺀 값과 같습니다.

이번 시즌에 얻을 수 있는 최대 수익을 결정하는 프로그램을 작성하세요.

입력

첫 번째 줄에는 n, m, p가 공백으로 구분되어 주어집니다.

다음의 n행에는 x_i와 a_i가 공백으로 구분되어 주어집니다. (0 < x_1 < x_2 < ... < x_n \leqq 1,000,000,000, 0 < a_i \leqq 1,000,000)

다음의 m행에는 y_j, b_j, c_j가 공백으로 구분되어 주어집니다. (0 < y_1 < y_2 < ... < y_m \leqq 1,000,000,000, 0 < b_j, c_j \leqq 1,000,000)

[부분문제]

#1(20점) : 1 \leqq n, m \leqq 1,000

#2(61점) : 1 \leqq n, m \leqq 50,000

#3(19점) : 1 \leqq n, m \leqq 500,000

출력

가능한 최대 이익을 첫 번째 줄에 출력하세요.

고기잡이
서브태스크

1초 512MB