아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

낚시를 할까 말까

시간 제한1초메모리 제한512 MB

요약
강을 따라 올라갈 때만 연료비를 내며 어획 지점과 판매 지점을 골라 이익을 최대로 만드는 문제입니다.
난이도

어려움10점 중 8점

유형
그리디, 정렬, 누적 합, 동적 계획법
정답자
아직 제출이 없습니다

문제

카마 강에서 조업하는 어선의 선주들이 여름 시즌에 사업을 최적화하기로 했다.

이들은 강 하구에서 x1,x2,…,xnx_1, x_2, \ldots, x_n킬로미터 떨어진 nn개의 지점에서 낚시할 수 있는 시즌 허가를 받았다. 번호 ii인 지점에서는 최대 aia_i톤의 물고기를 잡을 수 있다.

잡은 물고기는 강 하구에서 y1,y2,…,ymy_1, y_2, \ldots, y_m킬로미터 떨어진 mm개의 도매 기지에 팔 수 있다. 번호 jj인 기지는 이번 시즌에 최대 bjb_j톤의 물고기를 톤당 cjc_j루블에 사들일 수 있다.

하구에서 낚시 지점과 도매 기지까지의 거리는 강을 따라 측정한다.

어선은 강 하구에서 출발하여 시즌이 끝난 후 같은 곳으로 돌아와야 한다. 시즌 동안 어선은 강을 따라 자유롭게 오르내리며 낚시나 판매를 위해 멈출 수 있다. 어선의 적재량은 잡은 물고기를 얼마든지 실을 수 있을 만큼 충분하다. 하구에서 멀어질 때 어선은 물살을 거슬러 이동하며 1킬로미터당 pp루블의 연료비를 쓴다. 하구 쪽으로 이동할 때는 물살을 타므로 연료를 쓰지 않는다.

시즌이 끝난 후 어획 이익은 판매한 물고기의 총 가치에서 사용한 연료의 총 비용을 뺀 값과 같다.

시즌 동안 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하라.

입력

첫째 줄에는 세 정수 nn, mm, pp가 주어진다. 이는 낚시 지점의 수, 도매 기지의 수, 연료 가격이다 (1≤n,m≤500 0001 \le n, m \le 500\,000; 0≤p≤1090 \le p \le 10^9).

다음 nn개의 줄에는 두 정수 xix_i와 aia_i가 주어진다. 이는 각 낚시 지점의 하구로부터의 거리와 최대 어획량이다 (0<x1<x2<…<xn≤1090 < x_1 < x_2 < \ldots < x_n \le 10^9; 0<ai≤1060 < a_i \le 10^6).

다음 mm개의 줄에는 세 정수 yjy_j, bjb_j, cjc_j가 주어진다. 이는 각 도매 기지의 하구로부터의 거리, 최대로 사들이는 물고기의 톤수, 톤당 매입 가격이다 (0<y1<y2<…<ym≤1090 < y_1 < y_2 < \ldots < y_m \le 10^9; 0<bj,cj≤1060 < b_j, c_j \le 10^6).

출력

가능한 최대 이익을 나타내는 정수 하나를 출력한다.

힌트

두 번째 예제에서 최적의 행동은 다음과 같다. 하구에서 6킬로미터 떨어진 지점까지 이동하며 연료비 600루블을 쓰고, 그 지점에서 물고기 5톤을 잡는다. 그런 다음 강을 따라 1킬로미터 내려가 하구에서 5킬로미터 떨어진 기지에서 잡은 물고기를 톤당 2000루블에 판다. 그 후 하구로 돌아온다. 총이익은 9400루블이다.

예제3

  1. 예제 1

    입력
    3 2 0
1 5
2 3
4 5
2 2 10
3 6 5
    예상 출력
    50

  2. 예제 2

    입력
    2 1 100
6 5
100 4
5 100 2000
    예상 출력
    9400

  3. 예제 3

    입력
    3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2
    예상 출력
    2441