For an exam-day printing queue, each job has a deadline and takes exactly one time slot on the single printer — Mitu wants to schedule jobs to MAXIMIZE total priority points earned before deadlines are missed. Given N jobs, each with a deadline and a profit, and each job takes exactly 1 unit of time on a single machine, schedule jobs (each job must finish by its deadline or be skipped) to MAXIMIZE total profit. Print the maximum achievable profit.
Input
Line1: N. Next N lines: deadline profit.
Output
Maximum total profit.
Constraints
1 ≤ N ≤ 10^5, 1 ≤ deadline ≤ N
Sample Input
4 2 100 1 19 2 27 1 25
Sample Output
152
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.