Job Scheduling

There are $n$ independent, indivisible jobs numbered from $1$ to $n$. They are executed one after another in some order with no idle time between them, starting at time $t = 0$. The later a job starts, the longer it takes: if job $i$ starts at time $t$, its execution takes $h_i(t) = a_i t + b_i$, where $0 \le a_i \le 1$ and $0 \le b_i \le 1$. Each job therefore advances the clock from $t$ to $t + h_i(t) = (1 + a_i)\,t + b_i$.

The total execution time is the moment the last job finishes. Your task is to order the jobs so that this total is as small as possible.

Write a program that reads $n$ and the coefficients $a_i$, $b_i$ of every job, then prints an ordering of the jobs that minimizes the total execution time. If several orderings achieve the minimum total time, print the lexicographically smallest one (compare the sequences of job numbers position by position).

• The first line contains one integer $n$ $(1 \le n \le 10{,}000)$, the number of jobs.
• Each of the next $n$ lines contains two nonnegative real numbers $a_i$ and $b_i$ $(0 \le a_i \le 1,\ 0 \le b_i \le 1)$, separated by a single space. Each number is written in standard decimal form with exactly six digits after the decimal point. Line $i$ (of these $n$ lines) gives the coefficients of job $i$.

Print the chosen ordering of the jobs as a permutation of $1, \dots, n$, one job number per line. When more than one ordering yields the minimum total execution time, print the lexicographically smallest such ordering.