작업 스케줄링

면접 대비

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

요약

각각 한 단위 시간이 걸리는 작업들이 마감 시각과 이익을 가질 때, 이익의 합이 최대가 되도록 작업 일부를 골라 배치한다.

난이도: 보통10점 중 6점
유형: 그리디, 힙, 정렬, 구간
정답자: 아직 제출이 없습니다

문제

농부 존은 해야 할 일이 정말 많습니다! 농장을 효율적으로 운영하려면 그는 자신이 하는 각 작업으로 돈을 벌어야 하며, 각 작업은 정확히 한 단위 시간이 걸립니다.

그의 하루 일과는 시각 0에 시작하며 총 1,000,000,000 단위 시간으로 이루어집니다. 그는 현재 1번부터 $N$ 번까지 번호가 매겨진 $N$ 개(1 ≤ $N$ ≤ 100,000)의 작업 중에서 원하는 것을 골라 할 수 있습니다. 한 단위 시간에는 오직 하나의 작업만 할 수 있고 마감 시한이 촘촘하게 몰려 있어 모든 작업을 끝내지 못하는 경우가 대부분이지만, 아주 드물게는 $N$ 개 작업을 전부 끝낼 시간이 있을 수도 있습니다.

작업 $i$ 에는 마감 시한 $D_i$ (1 ≤ $D_i$ ≤ 1,000,000,000)가 있습니다. 그 시한까지 작업 $i$ 를 끝내면 이익 $P_i$ (1 ≤ $P_i$ ≤ 1,000,000,000)를 얻습니다.

주어진 작업과 마감 시한 목록에서 존이 얻을 수 있는 최대 총이익은 얼마일까요? 정답은 32비트 정수 범위를 벗어날 수 있습니다.

입력

첫째 줄: 정수 $N$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에는 공백으로 구분된 두 정수 $D_i$ 와 $P_i$ 가 주어집니다.

출력

첫째 줄: 존이 얻을 수 있는 최대 총이익을 나타내는 정수 하나.

힌트

마감 시한이 이른 작업부터 정렬한 뒤, 지금까지 고른 작업의 이익을 최소 힙에 넣습니다. 고른 작업 수가 현재 마감 시한을 초과하면 이익이 가장 작은 작업을 빼냅니다. 예를 들어 마감 1·이익 7인 작업을 시각 1에, 마감 2·이익 10인 작업을 시각 2에 처리하면 총이익 7 + 10 = 17을 얻습니다.

예제1

예제 1
입력
```
3
2 10
1 5
1 7
```
예상 출력
```
17
```