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

1041. Никифор

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Никифор решил подарить декану математико-механического факультета УрГУ линейно-независимую систему векторов (как вы знаете, мы только что отмечали юбилеи университета и факультета). В магазине продаются M штук N-мерных векторов. Для i-го вектора известна его цена ci. Никифор хочет купить N линейно-независимых векторов, заплатив за них минимальную сумму денег.
Напишите программу, которая определит, какие векторы Никифор должен купить, или сообщит, что нужную систему купить невозможно.

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

Первая строка содержит целые числа M и N (3 ≤ N ≤ 50; NM ≤ 2000). Следующие M строк содержат векторы, выставленные на продажу. Все координаты векторов являются целыми числами, по модулю не превышающими 2000. Следующие M строк содержат цены ci, по одной цифре в каждой строке. Цены представляют собой положительные целые числа, не превышающие 15 000.

Результат

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

Пример

исходные данныерезультат
5 3
1 0 0
0 1 0
0 0 1
0 0 2
0 0 3
10
20
30
10
10
40
1 
2 
4
Автор задачи: Дмитрий Филимоненков
Источник задачи: Пятый командный чемпионат УрГУ по программированию (Октябрь 2000 г.)