Задача C. Штамповка заготовок

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

На Заводе по изготовлению кухонной утвари перешли на сдельно-премиальную оплату труда. Рабочие цеха никелированных изделий Михаил и Александр решили оптимизировать свою работу и сократить время изготовления изделий.

Процесс изготовления изделия состоит из двух этапов: штамповка заготовки и никелирование. Штамповщик производит i-ую заготовку за время pi, причем одновременно он может изготавливать только одну заготовку. Затем второй рабочий укладывает изделие в ванну, где происходит его никелирование химическим методом за время qi. Одновременно в ванне может находиться несколько заготовок.

Напишите программу, которая поможет Михаилу и Александру определить последовательность штамповки заготовок, чтобы сделать суммарное время выполнения их работы минимальным (время считается от момента начала работы и до окончания процесса никелирования последнего изделия).

Формат входных данных

Первая строка входных данных содержит целое положительное число N – количество изделий, которые нужно изготовить, N не превосходит 105. Далее приведены N строк, содержащих время штамповки pi и время никелирования qi для каждой заготовки, где pi и qi – целые положительные числа, не превосходящие 1000.

Формат выходных данных

Программа должна вывести последовательность номеров заготовок, в соответствии с которой их должен делать штамповщик. Последовательность является некоторой перестановкой чисел от 1 до N.

Примеры тестов

Стандартный вход Стандартный выход
1
3
10 30
10 10
20 25
1 3 2

0.117s 0.028s 15