Губернатор

Вам, как губернатору города, необходимо организовать в своем городе постройку нескольких зданий, чтобы привести его в соответствие мировым стандартам. Губернатор вы не простой, а с высшим экономическим образованием, поэтому Вас в первую очередь заботит денежная сторона вопроса. Создав комиссию по этому поводу и проведя первое заседание, вы выяснили следующее.

В настоящее время, то есть до постройки требуемых зданий, город приносит стабильный доход – K золотых монет в месяц. Однако постройка любого здания может существенно изменить сложившееся положение.

Пронумеруем здания, требующие постройки числами от 1 до N, где N – их количество. Каждое здание i характеризуется двумя числами. Во-первых, это число a_i – его эффективность. Она является вещественным числом и обозначает то, во сколько раз возрастет текущая прибыль при постройке этого здания. Второй параметр b_i – это количество золотых монет, которые каждый месяц уходят на содержание этого здания. В итоге, если к моменту постройки i-го здания месячный доход составлял X монет, то после постройки этого здания его величина станет равна a_i•X – b_i. Отметим, что итоговый доход не обязательно будет целым числом.

Следует также учесть, что комитет по городскому строительству имеет сравнительно небольшой и мало обученный штат. Нехватка квалифицированных административных кадров проявляется прежде всего в том, что строители не могут работать над двумя проектами одновременно, а начав работу над одним зданием, не могут перейти к другому, не закончив первое.

Перед комиссией теперь стоит нелегкая задача: решить, в каком порядке строить здания – а строить их надо все, даже те, которые невыгодны – чтобы получать максимальный доход после постройки всех зданий. Как и следовало ожидать, для ваших коллег это оказалось слишком сложной задачей. Помогите им!

Входные данные

В первой строке входного файла INPUT.TXT записаны через пробел два целых числа N и K (1 ≤ N ≤ 10 000, 1 ≤ K ≤ 10⁶). Далее, в каждой из N последующих строк описано по зданию. Каждое описание имеет вид a_i b_i, где число a_i – вещественное (0 ≤ a_i ≤ 10), а b_i – целое (0 ≤ b_i ≤ 100). i-ая из строк файла соответствует (i−1)-му зданию в нумерации, используемой комиссией.

Выходные данные

В выходной файл OUTPUT.TXT выведите перестановку из N чисел от 1 до N, по одному числу на строку – номера зданий в порядке их постройки. Если существует несколько перестановок, максимизирующих прибыль, разрешается вывести любую.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]