Неумолкающий Янпул

«Быть спокойным – это не значит совсем ничего не делать»
(с) Джеки Чан

Ян — большой любитель поговорить. Он хочет сказать Давиду что-то очень важное. Известно, что Давид готов слушать Яна в течение следующих n минут. Яну нужно ровно t минут, чтобы высказать все, что он думает. Он также знает, что если заговорит в минуту i, то потратит энергию равную величине b_i, а Давид будет раздражаться на величину a_i. Обратите внимание, что если в минуту i Ян молчит, то он не тратит энергию, а Давид не раздражается.

Назовем напряженностью атмосферы общения величину, равную сумме итоговой раздраженности Давида и итоговой потраченной энергии Яна. Естественно, Ян хочет минимизировать напряженность атмосферы, так как хочет провести время с Давидом в приятной обстановке.

Их знакомый перспективный олимпиадник Егор очень хочет помочь им в этом. Но у него куча дел! К тому же, вот-вот начнется ВКОШП 2019 Восточно-Сибирского региона, который Егор никак не может пропустить. Взвесив все за и против, Егор поручает эту задачу вам.

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и t — количество минут, в течение которых Давид готов слушать Яна, и сколько минут нужно Яну, чтобы высказать Давиду все, что он думает (1 ≤ t ≤ n ≤ 10⁵).

Следующие n строк содержат по два целых числа a_i и b_i (0 ≤ a_i, b_i ≤ 10⁹) — величина раздражения Давида, и потраченная энергия Яна, если Ян заговорит в минуту i (1 ≤ i ≤ n).

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

В первой строке выходного файла OUTPUT.TXT нужно вывести минимальную напряженность, которую возможно достичь. Вторая строка должна содержать t чисел в порядке возрастания — номера минут, в которые Яну следует говорить, чтобы достичь эту напряженность. Если ответов несколько, разрешается вывести любой.

Пример

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

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