Problem D
Profitable Pizzas
A new app available in Calgary allows people to sign-up to deliver pizzas in exchange for money. Every first of the month, a new list of pizzas to deliver is available. Each entry on the list contains the amount of money the delivery-person will earn to deliver the pizza, and the deadline in seconds by which the pizza must be delivered. If the pizza is delivered after the deadline, the delivery-person does not receive any money. Each pizza takes one second to deliver and only one can be delivered per second. You are the first person to login to this new app every month and can select all the pizzas you want to deliver before everyone else. You’d like to maximize the amount of money you can make from a given delivery list.
Write the algorithm to find that maximum.
Input
The first line contains a single integer $1 \leq N \leq 2\cdot 10^5$, the number of pizzas to be delivered.
It is followed by $N$ lines, each containing an integer $1 \leq t_ i \leq 2\cdot 10^6$ representing the deadline by which the pizza must be delivered, followed by a space, followed by an integer $1 \leq d_ i \leq 100$ representing the amount of money paid for delivering the pizza before the deadline.
Output
For each query, output the maximum amount of money you can get for delivering the pizzas before the deadline.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 1 2 2 3 3 4 4 5 5 |
15 |
