Work Scheduling

Interview

Time limit1sMemory limit128 MB

Summary

Given jobs each taking one unit of time with a deadline and a profit, choose a subset to schedule so total profit is maximized.

Level: Medium6 of 10
Topics: Greedy, Heap, Sorting, Intervals
Solved: No attempts yet

Problem

Farmer John has so very many jobs to do! To run the farm efficiently, he must earn money on each job he does, and every job takes exactly one unit of time.

His workday starts at time 0 and lasts for 1,000,000,000 units of time. He can currently choose from any of $N$ (1 ≤ $N$ ≤ 100,000) jobs, conveniently numbered 1.. $N$ . It is possible but extremely unlikely that he has time for all $N$ jobs, since he can work on only one job during any single unit of time and the deadlines tend to be clustered so that he cannot complete every task.

Job $i$ has a deadline $D_i$ (1 ≤ $D_i$ ≤ 1,000,000,000). If he finishes job $i$ by that time, he earns a profit of $P_i$ (1 ≤ $P_i$ ≤ 1,000,000,000).

What is the maximum total profit Farmer John can earn from a given list of jobs and deadlines? The answer might not fit in a 32-bit integer.

Input

Line 1: A single integer $N$ .
Lines 2.. $N+1$ : Line $i+1$ contains two space-separated integers $D_i$ and $P_i$ .

Output

Line 1: A single integer, the maximum total profit Farmer John can earn.

Hint

Sort the jobs by their deadlines, then push each candidate job's profit onto a min-heap. Whenever the number of chosen jobs would exceed the current deadline, remove the least profitable one. For instance, doing the job with profit 7 (deadline 1) at time 1 and the job with profit 10 (deadline 2) at time 2 yields the maximum total of 7 + 10 = 17.

Examples1

Example 1
Input
```
3
2 10
1 5
1 7
```
Expected output
```
17
```