A humanitarian association received a shipment of containers with goods to be distributed among the population of a remote village, victim of cataclysm. All containers have been unloaded in the same day on a distant seaport from the village and the only available transport is an old truck, that takes one day for each round trip. This means that the truck can deliver a single container each day. Since each container has perishable goods, with a common expiration date, the association must devise a strategy to transport and distribute these goods, minimizing the loss.
Given N containers with expiration dates T_{i}, …, T_{N} and values V_{1}, …, V_{N}, your task is to find the optimal scheduling for the transportation such that the loss is minimum, i.e., the sum of values V_{i} for all containers not delivered in time is minimum. Assume that the expiration date is in days counted from the unloading at the seaport, i.e., a container i with T_{i} = 2 means that it must be delivered at most on the second day after being unloaded at the seaport. When deciding among containers with the same value, you should consider first the one with smaller id i.
The number of containers N in the first line followed by N lines with the information for each container. The information for each container consists of the the expiration date T_{i} and the value V_{i}, separated by a single space.
The containers come ordered by their ids. That is, the first container has id=1, the second container has id=2 and so on until the last line of input which describes container with id=N. There can be several containers with the same expiration date, and several containers with the same value.
The list of containers, one per line, to be delivered in time, sorted accordingly to their id.
1 ≤ N ≤ 100,000 | Number of containers |
1 ≤ T_{i} ≤ N | Expiration date of each container |
1 ≤ V_{i} ≤ 100,000 | Value of each container |
7 3 60 3 40 3 80 5 70 5 85 5 90 7 10
1 3 4 5 6 7
7 1 10 4 10 2 5 1 20 1 30 5 30 3 20
2 3 5 6 7
MIUP'2012, 20 de Outubro, DCC/FCUP
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.