Посольство
Перед финалом крупного международного турнира по программированию участники со всех регионов Украины съехались в Киев, чтобы в американском посольстве получить визу. Как известно, в американских посольствах с участниками соревнований по программированию работает ровно один чиновник, так что ничего удивительного, что образовалась огромная очередь из участников. Собеседование чиновника с каждым участником длится ровно один час. Участники взяли билеты из Киева заранее и некоторые из них могут не успеть на поезд из-за того, что им придётся стоять в очереди. Спонсоры турнира готовы компенсировать участникам, не успевшим на поезд, затраты на обмен билета.
Ваша задача - расставить финалистов в очереди так, чтобы затраты спонсора были минимальны.
Входные данные
Пусть N - количество финалистов, i - номер, под которым финалист зарегистрирован в системе, d_{i }- наиболее позднее время начала собеседования, после которого i-й финалист ещё может успеть на поезд, w_i - стоимость обмена билета для i-го финалиста.
В первой строке входного файла задано N, в последующих N строках заданы соответственно d_i и w_i (в i-й из этих строк).
Все числа во входном файле целые, положительные и не превышают 30000.
Выходные данные
Выведите оптимальную с точки зрения затрат спонсора очредь. В i-й строке вывода должен быть выведен номер участника, стоящего в очереди на i-м месте. Если таких очередей несколько, можно вывести любую из них.