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.

Task

Given N containers with expiration dates T_i, …, T_N and values V₁, …, 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.

Input

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.

Output

The list of containers, one per line, to be delivered in time, sorted accordingly to their id.

Constraints

Input example 1

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

Output example 1

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^AT_EX by H^EV^EA.