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