Задача №3585. Народный IPO
Компания «Рога и копыта» решила провести народный IPO (первоначальное публичное предложение акций компании на продажу широкому кругу лиц). Как обычно у Остапа Бендера не обошлось без аферы.
Потенциальные покупатели прислали заявки на покупку. Каждая заявка содержит два числа: процент акций компании, который хотел бы купить этот человек, а также цену, которую он готов заплатить за 1 процент акций.
Суть аферы заключается в следующем: Остап Бендер решил удовлетворить все заявки, но продавать каждому покупателю не процент от общего количества акций компании, а процент от еще не распроданной части. Остап Бендер чтит уголовный кодекс и деньги с покупателя может брать только за определенное количество проданных акций (а не за абстрактные доли от остатка и другие изобретенные им вещи).
Тем не менее, изменяя порядок удовлетворения заявок покупателей можно влиять на количество вырученных денег. Помогите Остапу Бендеру наиболее выгодно продать «Рога и копыта». Акций у компании так много, что Остап может продать любой процент акций, в том числе дробный.
В первой строке задано количество людей, подавших заявки N (1 ≤ N ≤ 1000). Далее следуют N строк по два числа в каждой: натуральное число, не превосходящее 100 — часть компании в процентах, которую хочет купить очередной человек и натуральное число не превоходящее 109 — количество денег, которое он заплатит за 1 процент от общего количества акций компании.
Выведите N чисел — номера людей в порядке, в котором должны удовлетворяться их заявки. Номера людей соответствуют порядку их описания во входных данных. Нумерация начинается с 1. Если решений несколько — выведите любое из них.
В первом тесте выгоднее сначала удовлетворить заявку второго человека, в результате чего будет продано 25% акций компании. Первому человеку будет продано 25% от оставшейся части (т.е. 18,75% от общего числа акций). Суммарная выручка в таком случае составит 25 × 10 + 18, 75 × 5 = 343, 75 рублей.
2 25 5 25 10
2 1
3 10 30 20 15 30 10
1 2 3