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

Чемпионат УрГУ 2000

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

E. Nikifor

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Nikifor has decided to present the dean of the Department of Mathematics and Mechanics with a linearly independent vector system (you know, that we’ve just celebrated jubilees of the University and of the Department). A store sells M items of N-dimensional vectors, 3 ≤ NM ≤ 2000; N ≤ 50. For each vector its price ci is known, 0 < iM. Nikifor wants to buy N linearly independent vectors paying for them minimal sum of money.

Задача

Write a program that would determine which vectors Nikifor should buy or would inform that it is impossible to satisfy his requirements.

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

The first line of an input contains numbers M and N separated with a space. The next M lines contain the vectors on sale. All of the coordinates are integers with an absolute value not exceeding 2 000. The numbers are separated from each other with a space. The next M lines contain prices ci, one number in each line. The prices are positive integers not exceeding 15 000.

Результат

The first line of an output should contain the minimal amount of money that Nikifor is to pay or the number 0, if Nikifor’s requirements cannot be satisfied in this store. If it is possible to make a purchase, then the next N lines should contain the numbers of the vectors that Nikifor should buy. If several sets of such numbers are possible, then you should write one of them which is minimal according to the lexicographic order.

Пример

исходные данныерезультат
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 г.)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1041. Nikifor