Olimpiada Informatyczna

Niebieskie ksi.eczki

II Olympiad in Informatics 1994/1995

Task: SZE

Author: Marcin Jurdziński

Job Scheduling

III stage contest

We are given n independent and indivisible jobs numbered from 1 to n. They should be executed sequentially in any order. The later the execution of a job starts the longer it lasts - precisely, the time of execution of the job i is h_i(t)=a_it+b_i, if we start it in the moment t. We assume that 0<=a_i<=1, 0<=b_i<=1.

The goal is to schedule the jobs so that the total execution time is the shortest.

Task

Write a program that:

reads from the text file SZE.IN the number of jobs n not greater than 10000 and successively - for each job i - the coefficients a_i and b_i determining the dependence of the job execution time upon the time it starts,
finds such a scheduling of the jobs that the cumulative execution time is minimal; then the program writes to the file SZE.OUT the numbers of the jobs in the order they should be executed.

Input

In the first line of the file SZE.IN there is one positive integer not greater then 1000. It is the number of jobs n.
In each of the following n lines there is a pair of nonnegative real numbers. The numbers are written in a standard form with a decimal point and six digits after the point. The numbers are separated by a single space. It is the pair of coefficients a_i and b_i determining the dependence of the execution time of the corresponding i-th job upon the time it starts.

Output

One should write in the file SZE.OUT the scheduling of the jobs, i.e. an appropriate permutation of numbers 1,...,n; one number per line.

Example

For the file SZE.IN:

5
0.002000 0.003000
0.016000 0.001000
0.100000 0.300000
0.016000 0.005000
0.030000 0.060000

in the file SZE.OUT one should write:

Your program should look for the file SZE.IN in the current directory and create the file SZE.OUT also in the current directory. The source file containing the program written by you should be named SZE.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file SZE.EXE.