Задача сапожника
Сапожнику необходимо выполнить n работ. Каждый день сапожник может выполнять только одну работу. Для каждой i - ой работы известно время ее выполнения в днях T[i] и штраф S[i], который каждый день должен платить сапожник до тех пор, пока он не отдаст i - ую работу заказчику. Найти последовательность выполнения работ, при которой сумма штрафа будет минимальной.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит количество работ n (1 ≤ n ≤ 1000), за которой следуют n строк, содержащие характеристики работ T[i] (1 ≤ T[i] ≤ 1000) и S[i] (1 ≤ S[i] ≤ 10000).
Выходные данные
Для каждого теста в отдельной строке вывести порядок работ, при котором сумма штрафа минимальна. При существовании нескольких оптимальных порядков работ выводить лексикографически наименьший.