Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 2 сек. Память: 32 Мб Сложность: 31%)

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

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

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
15 3
5 9
1 7
4 6
2 3
0 8
21
2 4 5

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Переполох у турникетов
 B. Поездка в кино
 C. Баобаб
 D. Очистка террасы
 E. Битва школ
 F. Этажи
 G. Космическое сновидение
 H. Неумолкающий Янпул
 I. ЦПСП
 J. Стреляй!
 K. Отряд Стёпы
 L. Swap optimization

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru