ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest October'2005

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Courier

Time limit: 1.0 second
Memory limit: 64 MB
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.


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.


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.


1 17
5 15
2 10
2 11
1 4 2
Problem Author: Nikita Rybak
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)
To submit the solution for this problem go to the Problem set: 1403. Courier