問題
이 문제에서 당신은 인류가 태초부터 풀지 못했던 가장 심오한 도전 중 하나를 해결하게 된다 — 바로 큰돈을 버는 방법이다.
당신은 위젯 시장의 중개인이다. 당신의 일은 위젯 생산 회사에서 위젯을 사서 위젯 소비 회사에 파는 것이다. 각 소비 회사는 어떤 종료일까지 하루에 위젯 하나를 구매하겠다는 공개 요청과 구매 가격을 가지고 있다. 반면 각 생산 회사는 위젯을 공급할 수 있는 시작 날짜와 위젯 하나당 공급 가격을 가지고 있다.
공정 경쟁법 때문에, 당신은 생산 회사 하나와 소비 회사 하나와만 계약을 맺을 수 있다. 당신은 생산 회사가 공급을 시작할 수 있는 날부터 소비 회사가 지정한 날짜까지, 하루에 하나씩 위젯을 구매한다. 그 기간의 각 날마다 생산 회사의 판매 가격과 소비 회사의 구매 가격의 차이를 이익으로 얻는다.
당신의 목표는 이익을 최대화하는 소비 회사와 생산 회사를 선택하는 것이다.
入力
입력의 첫 줄에는 생산 회사의 수 m과 소비 회사의 수 n (1 ≤ m, n ≤ 500 000)이 주어진다. 이어서 m줄이 주어지며, i번째 줄에는 두 정수 pi와 di (1 ≤ pi, di ≤ 109)가 있다. 이는 i번째 생산 회사가 위젯 하나를 pi달러에 판매하며 di일에 첫 위젯을 공급할 수 있음을 의미한다. 그 다음 n줄이 주어지며, j번째 줄에는 두 정수 qj와 ej (1 ≤ qj, ej ≤ 109)가 있다. 이는 j번째 소비 회사가 위젯을 qj달러에 구매하며, ej일은 해당 회사에 마지막 위젯이 배송되어야 하는 날의 바로 다음 날임을 의미한다.
出力
벌 수 있는 총 달러의 최대값을 출력하라. 이익이 되는 계약을 맺을 방법이 없다면 0을 출력하라.
例題 #1
2 2
1 3
2 1
3 5
7 2
5
例題 #2
1 2
10 10
9 11
11 9
0
ログインしないとコードを書けません。