호텔

시간 제한4초메모리 제한128 MB

요약

용량과 유지비가 있는 방들과 제시 금액 및 최소 용량이 있는 예약 요청들이 주어질 때, 최대 o개의 요청을 방에 배정해 총 수익에서 유지비를 뺀 이익을 최대화합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 힙, 정렬
정답자: 아직 제출이 없습니다

문제

친구가 바닷가 도시에 호텔을 운영합니다. 성수기가 시작되면서 손님들의 예약 신청이 쏟아지자, 친구는 예약 시스템을 만드는 일을 여러분에게 부탁했습니다.

호텔에는 대여 가능한 방이 $n$ 개 있습니다. $i$ 번째 방은 손님을 받았을 때만 유지비 $c_i$ 가 들며, 최대 $p_i$ 명을 수용할 수 있습니다. 유지비는 수용 인원에 대해 단조롭습니다. 즉 어떤 방의 유지비는 그보다 더 적은 인원을 수용하는 방(수용 인원이 더 작은 방)의 유지비보다 결코 저렴하지 않습니다.

예약 시스템에는 여러 개의 신청이 들어옵니다. $j$ 번째 신청은 하루 동안 방 하나를 빌리는 대가로 지불할 금액 $v_j$ 와, 요구하는 방의 최소 수용 인원 $d_j$ 를 명시합니다. 각 신청은 방 하나에만 배정할 수 있고, 각 방은 신청 하나만 받을 수 있습니다. 배정되는 방은 반드시 그 신청의 최소 수용 인원 이상이어야 합니다. 친구는 최대 $o$ 개의 신청까지만 받기로 했습니다.

받은 신청 중 일부를 골라 배정했을 때 친구가 얻을 수 있는 최대 이익(대여로 받은 금액의 합에서 사용한 방들의 유지비 합을 뺀 값)을 구하세요.

입력

첫 번째 줄에 세 정수 $n$ , $m$ , $o$ 가 주어집니다 ( $1 \le n, m \le 500\,000$ , $1 \le o \le \min(m, n)$ ). 각각 방의 수, 들어온 신청의 수, 받을 수 있는 신청의 최대 개수를 뜻합니다.

이어지는 $n$ 개의 줄에는 방의 정보가 주어지며, $i$ 번째 줄에는 두 정수 $c_i$ , $p_i$ 가 주어집니다 ( $1 \le c_i, p_i \le 10^9$ ). 각각 방의 유지비와 수용 인원을 뜻합니다.

이어지는 $m$ 개의 줄에는 신청의 정보가 주어지며, $j$ 번째 줄에는 두 정수 $v_j$ , $d_j$ 가 주어집니다 ( $1 \le v_j, d_j \le 10^9$ ). 각각 제시한 대여 금액과 요구하는 최소 수용 인원을 뜻합니다.

출력

신청을 최대 $o$ 개까지 받아서 얻을 수 있는 최대 이익을 정수 하나로 출력합니다. 어떤 신청도 받지 않는 것이 가장 이득이라면 $0$ 을 출력합니다. 이익은 매우 커질 수 있습니다.

예제7

예제 1

입력

예상 출력

예제 2
입력
```
1 1 1
5 3
10 2
```
예상 출력
```
5
```
예제 3
입력
```
2 1 1
3 2
4 3
100 5
```
예상 출력
```
0
```
예제 4
입력
```
2 2 2
10 2
20 3
5 1
8 1
```
예상 출력
```
0
```
예제 5
입력
```
3 3 1
1 5
1 5
1 5
10 1
20 1
15 1
```
예상 출력
```
19
```
예제 6
입력
```
2 1 1
3 5
7 5
10 4
```
예상 출력
```
7
```
예제 7
입력
```
2 2 2
2 2
10 5
8 1
20 5
```
예상 출력
```
16
```