L. Набор классификаторов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

При решении различных задач используются классификационные алгоритмы (или классификаторы), которые относят наблюдаемый объект к определённому классу. Например, рассмотрим запросные классификаторы, которые относят запрос пользователя в поисковую систему к той или иной группе запросов: спортивные события, новости, рецепты и пр. Такие классификаторы помогают улучшить взаимодействие пользователя с сервисом.

При внедрении классификаторов смотрят на метрики и на время работы. Метрики отвечают за пользу, которую классификаторы приносят сервису, а время работы должно быть небольшим — для удобства пользователя. Опытным путём было выявлено, что для быстрого и комфортного взаимодействия с поисковой системой, одновременно может работать не более $$$M$$$ классификаторов.

Всего есть $$$K$$$ метрик, которые определены для каждого классификатора. Для набора классификаторов значение метрики определяется как максимум по ней среди классификаторов, входящих в набор. Пользой набора классификаторов считается сумма его метрик.

Вам дано $$$N$$$ классификаторов. Необходимо найти набор из $$$M$$$ классификаторов с максимальной пользой.

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

Первая строка содержит три целых числа $$$N$$$, $$$M$$$ и $$$K$$$ ($$$1 \leqslant N \leqslant 2000$$$, $$$1 \leqslant M \leqslant N$$$, $$$1 \leqslant K \leqslant 15$$$) — количество классификаторов, размер искомого набора и количество метрик.

Следующие $$$N$$$ строк описывают классификаторы. В $$$i$$$-й строке содержатся $$$K$$$ значений метрик $$$a_{ij}$$$ ($$$1 \leqslant a_{ij} \leqslant 10^8$$$) $$$i$$$-го классификатора.

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

В первой строке выведите одно число — максимальную пользу, которую можно получить для набора из $$$M$$$ классификаторов. Во второй строке выведите через пробел $$$M$$$ чисел — номера классификаторов из набора с максимальной пользой.

Если таких наборов несколько, можно вывести любой.

Примеры
Входные данные
6 2 3
4 1 1
1 4 1
1 1 4
1 3 3
3 1 3
3 3 1
Выходные данные
10
1 4 
Входные данные
3 3 2
10 10
5 5
1 1
Выходные данные
20
1 2 3