Problem C: Humanitarian Logistics

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 Ti, …, TN and values V1, …, VN, your task is to find the optimal scheduling for the transportation such that the loss is minimum, i.e., the sum of values Vi 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 Ti = 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 Ti and the value Vi, 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,000Number of containers
1 ≤ TiNExpiration date of each container
1 ≤ Vi ≤ 100,000Value of each container

Input example 1

3 60
3 40
3 80
5 70
5 85
5 90
7 10

Output example 1


Input example 2

1 10
4 10
2 5
1 20
1 30
5 30
3 20

Output example 2


MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from LATEX by HEVEA.