Wstęp do programowania w C++

Danych jest n nieoznaczonych i niepodzielnych czynności, ponumerowanych od 1 do n. Należy je wykonać sekwencyjne w dowolnej kolejności. Wykonanie każdej czynności trwa tym dłużej im później rozpocznieniem - ściśle czas wykonania czynności i wynosi k(i) = a_i * t + b_i jeśli rozpoczęcie ja w chwili t. Zakładamy, że 0 ≤ a_i ≤ 1, 0 ≤ b_i ≤ 1.

Należy uszeregować czynności w takiej kolejności, aby łączny czas ich wykonania był najmniejszy.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę czynności n nie większą niż 10 000 oraz kolejno dla każdej czynności i - wspótczynniki a_i oraz b_i określające zależność czasu wykonania tej czynności od chwili jej rozpoczęcia,
• znajduje takie uszeregowanie czynności, żeby łączny czas ich wykonania był minimalny i zapisuje na standardowym wyjściu numeru czynności w takiej kolejności, w jakiej należy je wykonać.

Wejście

W pierwszej wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodająca nie większa niż 10 000. Jest to liczba czynności n. W każdym n kolejnym wierszu jest zapisana para liczb rzeczywistych nieujemnych w standardowej notacji z kropką i siescoma cyframi po kropce. Są to para współczynników a_i oraz tekst-b_i określających zależność czasu wykonania odpowiedniej i-tej czynności od chwili jej rozpoczęcia.

Wyjście

Na standardowym wyjściu należy zapisać uszeregowanie czynności, to znaczy odpowiednia permutacja liczb 1, ..., n każda liczba w osobnym wierszu.

Dla danych wejściowych:

5
0.002000 0.003000
0.016000 0.001000
0.100000 0.300000
0.016000 0.005000
0.030000 0.060000
poprawną odpowiedzią jest:

2
4
1
5
3