몰로코 빗코인 복권 (쉬운 버전)

몰로코는 매달 말에 직원 복지를 걸고 간단한 복권 추첨을 한다.

당신은 복권 $n$장을 받았고, $i$번 복권의 상금은 빗코인 $w_i$개다 ($w_i > 0$).

복권마다 동전이 하나씩 짝지어져 있다. $i$번 복권의 동전은 확률 $p_i$로 앞면이, 확률 $1 - p_i$로 뒷면이 나온다 ($0 < p_i < 1$). 동전 던지기는 모두 독립이다.

각 단계에서 아직 고르지 않은 복권 하나를 골라 상금을 즉시 받는다. 그다음 그 복권에 짝지어진 동전을 던진다. 앞면이 나오면 추첨이 이어져 복권을 하나 더 고르고, 복권이 다 떨어질 때까지 같은 과정을 반복한다. 뒷면이 나오면 추첨은 그 자리에서 끝나고 그때까지 모은 빗코인을 전부 가진다.

모든 $w_i$와 $p_i$를 알고 있다. 받는 빗코인의 기댓값을 최대로 만드는 복권 선택 순서를 구하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 1000$).

다음 $n$개 줄에 두 정수 $w_i$와 $q_i$가 주어진다 ($1 \le w_i \le 10000$, $0 < q_i < 10000$). 확률은 $p_i = q_i / 10000$으로 정의한다.

복권을 고르는 순서를 나타내는 순열을 한 줄에 출력한다. 순열은 $1$부터 $n$까지의 정수로 이루어진 길이 $n$의 수열이며, 수는 공백으로 구분한다.

기댓값을 최대로 만드는 순열이 여럿이면 사전순으로 가장 앞서는 것을 출력한다. 즉 앞쪽 자리일수록 작은 번호가 오도록 한다.

순서 $\pi$로 복권을 고를 때 받는 빗코인의 기댓값은 다음과 같다.

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

첫 번째 예제에서 순서 $(1, 2, 3)$의 기댓값은 $2 + 0.3 \times 5 + 0.15 \times 7 = 4.55$다. 기댓값을 최대로 만드는 순서는 $(2, 3, 1)$이고 그 값은 $8.7$이다.

세 번째 예제에서는 순서 $(2, 3, 1)$과 $(3, 2, 1)$의 기댓값이 같지만 $(2, 3, 1)$이 사전순으로 앞선다.