Freddy works as a courier for Vito Maretti. Once in the morning Freddy got an assignment to deliver N containers of whisky – every one to a different town of the state. It takes one day to deliver each container from the list. But each of the orders (one order – one container) is assigned its particular time of delivery and Freddy’s reward. If Freddy does not deliver an order in time he will get no reward and he even can be hauled over the coals. So there is no sense to deliver such orders. Help Freddy to compile an operating schedule that would yield the maximal profit – he won’t be in a hole.
Input
The first line contains the number of orders N (1 ≤ N ≤ 1000). Each of the next N lines contains two integers: the delivery time and Freddy’s reward. The delivery time is not less than 1 day and not more than 100000 days. The reward is from 1 to 100000 dollars.
Output
The first line should contain a number of orders that Freddy will deliver. The second line should contain a list of containers numbers in the order of their delivery separated with spaces. The out-of-date orders should not be delivered. If there are several solutions, output any of them.
Sample
input | output |
---|
4
1 17
5 15
2 10
2 11
| 3
1 4 2
|
Problem Author: Nikita Rybak
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)