Shoemaker's Job Order

Interview

Time limit2sMemory limit512 MB

Summary

Order N jobs to minimize the total fine paid while each job waits, using the shortest processing time per fine ratio first, with lexicographically smallest ties.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

A shoemaker has $N$ jobs ordered by customers waiting in his shop. He works on one job at a time, and job $i$ takes $T_i$ days to finish. $T_i$ is an integer with $1 \le T_i \le 1000$ .

For every day that passes before job $i$ starts, the shoemaker pays a fine of $S_i$ cents. $S_i$ is an integer with $1 \le S_i \le 10000$ . Find the job order that makes the total fine as small as possible.

Once an order is fixed, job $i$ starts after a delay equal to the sum of the durations of the jobs placed before it. The total fine is the sum, over all jobs, of that delay multiplied by $S_i$ .

The shoemaker cannot run two jobs on the same day. After he starts job $i$ , he cannot work on any other job until job $i$ is finished.

Input

The first line contains the integer $N$ with $1 \le N \le 1000$ .

The $i$ -th of the next $N$ lines contains $T_i$ and $S_i$ , separated by a space.

Output

Print, on one line, the job order that gives the smallest total fine. Each job is written as its input number from $1$ to $N$ , and consecutive numbers are separated by a single space. If several orders reach the smallest total fine, print the lexicographically smallest one.

Examples3

Example 1
Input
```
4
3 4
1 1000
2 2
5 5
```
Expected output
```
2 1 3 4
```
Example 2
Input
```
1
1000 10000
```
Expected output
```
1
```
Example 3
Input
```
2
1 10000
1000 1
```
Expected output
```
1 2
```