작업 스케줄링

$1$번부터 $n$번까지 번호가 매겨진, 서로 독립적이며 나눌 수 없는 작업 $n$개가 있다. 이 작업들은 중간에 쉬는 시간 없이 어떤 순서로든 하나씩 차례대로 실행되며, 시작 시각은 $t = 0$이다. 작업을 늦게 시작할수록 실행 시간이 길어진다. 즉, 작업 $i$를 시각 $t$에 시작하면 실행에 $h_i(t) = a_i t + b_i$의 시간이 걸리며, 여기서 $0 \le a_i \le 1$, $0 \le b_i \le 1$이다. 따라서 각 작업은 시각을 $t$에서 $t + h_i(t) = (1 + a_i)\,t + b_i$로 진행시킨다.

전체 실행 시간은 마지막 작업이 끝나는 시각이다. 이 전체 실행 시간이 최소가 되도록 작업 순서를 정하는 것이 목표이다.

$n$과 각 작업의 계수 $a_i$, $b_i$를 읽어, 전체 실행 시간을 최소로 만드는 작업 순서를 출력하는 프로그램을 작성하라. 전체 실행 시간이 최소가 되는 순서가 여러 개라면, 그중 사전순으로 가장 앞서는 것을 출력한다(작업 번호 수열을 앞에서부터 자리별로 비교한다).

• 첫째 줄에 작업의 개수 $n$ $(1 \le n \le 10{,}000)$이 주어진다.
• 이어지는 $n$개의 줄에는 각각 음이 아닌 실수 $a_i$와 $b_i$ $(0 \le a_i \le 1,\ 0 \le b_i \le 1)$가 공백 하나로 구분되어 주어진다. 각 수는 소수점 아래 정확히 여섯 자리까지 표기된 표준 십진수 형식이다. 이 $n$개 줄 중 $i$번째 줄은 작업 $i$의 계수를 나타낸다.

선택한 작업 순서를 $1, \dots, n$의 순열로, 한 줄에 작업 번호 하나씩 출력한다. 전체 실행 시간을 최소로 만드는 순서가 둘 이상이면, 그중 사전순으로 가장 앞서는 순서를 출력한다.