eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Dura Lex

Dura Lex

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Вася обожает заказывать новые гаджеты из-за границы. К сожалению, для Васи, недавно ввели новые правила таможенного контроля, согласно которым для получения каждого гаджета Васе нужно получить N справок. Получить каждую справку непросто — чтобы получить i-ю справку, нужно отстоять в очереди Di дней, причём одновременно можно стоять в очереди не более чем за одной справкой. И что самое обидное, в выдаче i-й справки отказывают с вероятностью Pi%, причём совершенно случайно, и более того, если в выдаче справки отказано, то все предыдущие справки автоматически аннулируются, и всё приходится начинать сначала. Хоть одно радует — справки можно получать в любом порядке.

Вася хочет получить новый гаджет во что бы то ни стало. Он будет пытаться собрать все справки, пока не добьётся успеха. Помогите ему выбрать порядок получения справок таким образом, чтобы минимизировать среднее время, за которое он соберёт их все.

Входные данные

Первая строка входного файла содержит целое число N . Следующие N строк содержат по два целых числа каждая: Di и Pi.

1 ≤ N ≤ 105

0 ≤ Di ≤ 1000

0 ≤ Pi < 100

Выходные данные

Выведите N целых чисел от 1 до N — искомую перестановку. Если оптимальных перестановок несколько, выведите лексикографически минимальную.

Пример

Входные данные #1
3
1 10
10 10
5 90
Выходные данные #1
3 1 2
Автор Евгений Капун
Источник Зимняя школа по программированию 2014, Харьков