ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1900. Машина счастья

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В то время как в далёком космосе люди летают между планетами и исследуют новые миры, жители Земли всё так же каждый день просыпаются с утра, едут на работу, вечером возвращаются домой и пытаются хоть как-то отдохнуть. И среди них всё больше зреет недовольство и зависть по отношению к тем, кто может себе позволить свободно летать в космос.
Правительство Земли такая ситуация не устраивает. Его цель — сделать абсолютно всех людей счастливыми. Но поскольку всех сразу счастливыми сделать сложно, решили начать с уездного города Люкс, а потом, в случае успеха, перенести полученный опыт на более крупные города.
Особенностью Люкса является то, что он расположен в длинном подземном тоннеле, и поэтому в нём ходит всего одна электричка. Этой электричкой ежедневно пользуется почти всё население города. Правительство приобрело машину по массовой промывке мозгов и установило её в электричке. Поскольку влияние машины на человека не до конца изучено, было решено ограничить количество перегонов между соседними станциями, на которых будет включаться машина. Уже собрана полная статистика по тому, сколько людей ежедневно проезжает между каждой парой станций. Осталось выбрать, на каких перегонах включать машину, чтобы осчастливить как можно больше людей.

Исходные данные

В первой строке записаны целые числа n и k — общее количество остановок электрички и количество перегонов, на которых было решено включать машину счастья (2 ≤ n ≤ 500; 1 ≤ kn − 1). В i-й из следующих n − 1 строк записаны ni целых чисел, j-е из которых обозначает количество пассажиров, входящих на станции i и выходящих на станции i + j. Эти числа неотрицательны и не превосходят 100. Следует считать, что каждый пассажир пользуется электричкой только один раз в день.

Результат

В первой строке выведите общее количество осчастливленных пассажиров. Во второй строке выведите k целых чисел в порядке возрастания — номера перегонов, на которых нужно включать машину счастья. Перегон между станциями i и i + 1 имеет номер i. Если задача имеет несколько решений, выведите любое из них.

Пример

исходные данныерезультат
4 1
5 0 6
5 3
5
14
3
Автор задачи: Алексей Самсонов (подготовка — Александр Фетисов)
Источник задачи: XVI Открытый чемпионат Урала по спортивному программированию (апрель, 2012)