| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 64 Мб | |
| Максимальный балл: | 100 |
На Заводе по изготовлению кухонной утвари перешли на сдельно-премиальную оплату труда. Рабочие цеха никелированных изделий Михаил и Александр решили оптимизировать свою работу и сократить время изготовления изделий.
Процесс изготовления изделия состоит из двух этапов: штамповка заготовки и никелирование. Штамповщик производит i-ую заготовку за время pi, причем одновременно он может изготавливать только одну заготовку. Затем второй рабочий укладывает изделие в ванну, где происходит его никелирование химическим методом за время qi. Одновременно в ванне может находиться несколько заготовок.
Напишите программу, которая поможет Михаилу и Александру определить последовательность штамповки заготовок, чтобы сделать суммарное время выполнения их работы минимальным (время считается от момента начала работы и до окончания процесса никелирования последнего изделия).
Первая строка входных данных содержит целое положительное число N – количество изделий, которые нужно изготовить, N не превосходит 105. Далее приведены N строк, содержащих время штамповки pi и время никелирования qi для каждой заготовки, где pi и qi – целые положительные числа, не превосходящие 1000.
Программа должна вывести последовательность номеров заготовок, в соответствии с которой их должен делать штамповщик. Последовательность является некоторой перестановкой чисел от 1 до N.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|