题目描述

$Nikifor$决定送给数学与力学系的系主任一组线性无关的向量系统（你知道，我们刚刚庆祝了大学和系的周年纪念）。商店出售m个n维向量，其中$m ≤ 2000，3 ≤ n ≤ m$。每个向量都有一个已知的价格ci，$0 < i ≤ m$。Nikifor希望购买n个线性无关的向量，并为此支付最少的钱。请编写一个程序，确定$Nikifor$应该购买哪些向量，或者告知他无法满足要求。

输入格式

输入的第一行包含两个用空格分隔的数字m和n。接下来的m行是出售的向量。所有坐标都是绝对值不超过$2000$的整数。数字之间用空格分隔。接下来的m行是价格ci，每行一个数字。价格是正整数，不超过$15000。$

输出格式

如果无法满足Nikifor的要求，则输出的第一行应为数字0。如果可以购买，则第一行输出Nikifor需要支付的最小金额，接下来的n行输出应购买的向量编号。如果有多个满足条件的向量组合，则输出字典序最小的那个。

示例输入1

5 3
1 0 0
0 1 0
0 0 1
0 0 2
0 0 3
10
20
30
10
10

示例输出1

40
1
2
4

来源

Ural State University Internal Contest October'2000 Students Session