Fast Sale
A supermarket has a set P of products on sale. It earns a profit px for each product x in P sold by a deadline dx, that is on one of the first dx days of the year. Otherwise it is worth nothing.
Also, the supermarced can sell only one product a day! You have to find the schedule for selling the products such that the profit is maximized.
InputThe first line will contians one integer N (1 <= N <= 20000), that is the number of products. Each of the next N lines contains two integers from the interval [1 10000] representing the price and the deadline for selling the product.
OutputPrint the profit that would be obtained with an optimal selling schedule.
Input:
Output:
4
50 2
10 1
20 2
30 1
Output:
80Input:
Output:
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10Output:
185Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.