문제
카마 강에서 물고기를 잡는 준혁이는 여름 시즌동안 사업을 최적화하기로 하였다.
준혁이는 강의 하류로부터 x1, x2, ... , xn 킬로미터 떨어진 지점에서 물고기를 잡을 권리를 받았다.
i번째 지점에서는 ai톤 이하의 물고기를 잡을 수 있다.
잡은 물고기는 강의 하류로부터 y1, y2, ... , ym 킬로미터 떨어진 지점에서 팔 수 있다.
j번째 지점에서는 톤당 cj원에 bj톤 이하의 물고기를 팔 수 있다.
어선은 강에서 자유롭게 오갈 수 있다.
단, 강의 상류로 올라갈 때에는 1km당 p원의 연료를 소모한다.
준혁이가 최대의 이익을 얻는다면, 총 몇 원의 수익을 낼 수 있는가?
입력
첫 번째 줄에 n, m, p가 공백으로 구분되어 주어진다. (1 ≤ n, m ≤ 500000, 0 ≤ p ≤ 109)
두 번째 줄 부터 n개의 줄에 걸쳐 xi, ai가 공백으로 구분되어 주어진다. (0 < x1 < x2 < ... < xn ≤ 109, 0 < ai ≤ 106)
이후 m개의 줄에 걸쳐 yj, bj, cj가 공백으로 구분되어 주어진다. (0 < y1 < y2 < ... < y<m ≤ 109, 0 < bj, cj ≤ 106)
출력
첫 번째 줄에 준혁이가 얻을 수 있는 최대 이익을 출력하여라.
예제 #1
3 2 0
1 5
2 3
4 5
2 2 10
3 6 5
50
예제 #2
2 1 100
6 5
100 4
5 100 2000
9400
예제 #3
3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2
2441
출처
Russian Olympiad in Informatics 2016
로그인해야 코드를 작성할 수 있어요.