Work Scheduling

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.

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

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

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.