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