Vitcoin Lottery at Moloco (Easy)

Interview

Time limit2sMemory limit512 MB

Summary

Order n tickets with prizes w_i and continuation probabilities p_i to maximize the expected sum of collected prizes, breaking ties by the lexicographically smallest permutation.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math, Probability
Solved: No attempts yet

Problem

At the end of every month Moloco runs a simple lottery for extra employee perks.

You receive $n$ lottery tickets, and ticket $i$ pays a prize of $w_i$ Vitcoins ( $w_i > 0$ ).

Each ticket is paired with its own coin. The coin of ticket $i$ comes up heads with probability $p_i$ and tails with probability $1 - p_i$ ( $0 < p_i < 1$ ). All coin flips are independent.

At each step you choose one ticket you have not chosen yet and claim its prize immediately. Then you flip the coin paired with that ticket. On heads the lottery continues and you choose another ticket, repeating until you run out of tickets. On tails the lottery ends at once and you keep every Vitcoin you have collected so far.

You know all values $w_i$ and $p_i$ . Find an order of picking the tickets that maximizes the expected number of Vitcoins you win.

Input

The first line contains an integer $n$ ( $1 \le n \le 1000$ ).

Each of the next $n$ lines contains two integers $w_i$ and $q_i$ ( $1 \le w_i \le 10000$ , $0 < q_i < 10000$ ). The probability is defined as $p_i = q_i / 10000$ .

Output

Print, on a single line, the permutation that describes the order in which you pick the tickets. The permutation has length $n$ , consists of the integers from $1$ to $n$ , and its entries are separated by single spaces.

If several permutations maximize the expected number of Vitcoins, print the one that comes first lexicographically, so the smaller index must come earlier.

Note

Picking the tickets in the order $\pi$ wins the following expected number of Vitcoins.

$\sum_{k=1}^{n} w_{\pi_k} \prod_{j < k} p_{\pi_j}$

In the first example the order $(1, 2, 3)$ has expectation $2 + 0.3 \times 5 + 0.15 \times 7 = 4.55$ . The order $(2, 3, 1)$ maximizes the expectation at $8.7$ .

In the third example the orders $(2, 3, 1)$ and $(3, 2, 1)$ have the same expectation, and $(2, 3, 1)$ comes first lexicographically.

Examples5

Example 1
Input
```
3
2 3000
5 5000
7 2000
```
Expected output
```
2 3 1
```
Example 2
Input
```
3
3 5000
5 1500
7 2000
```
Expected output
```
3 1 2
```
Example 3
Input
```
3
1 4000
1 5000
1 5000
```
Expected output
```
2 3 1
```
Example 4
Input
```
1
10000 9999
```
Expected output
```
1
```

Example 5

Input

Expected output

1 2 3 4 5