Задача швеця

Швецю необхідно виконати n робіт. Кожний день швець може виконувати тільки одну роботу. Для кожної i - ої роботи відомий час її виконання в днях T[i] та штраф S[i], який кожний день повинен платити швець до тих пір, поки він не віддасть i - ту роботу замовнику. Знайти послідовність виконання робіт, при якій сума штрафу буде мінімальною.

Вхідні дані

Складаються з декількох тестів. Перший рядок кожного тесту містить кількість робіт n (1 ≤ n ≤ 1000), за яким йдуть n рядків, що містять характеристики робіт T[i] (1 ≤ T[i] ≤ 1000) та S[i] (1 ≤ S[i] ≤ 10000).

Вихідні дані

Для кожного тесту в окремому рядку вивести порядок робіт, при якому сума штрафу мінімальна. При існуванні декількох оптимальних порядків робіт виводити лексикографічно найменший.

Приклади