ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2000

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Nikifor

Time limit: 1.0 second
Memory limit: 64 MB
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. For i-th vector its price ci is known. 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.

Input

The first line contains integers M and N (3 ≤ N ≤ 50; NM ≤ 2000). The next M lines contain the vectors on sale. All of the coordinates are integers with an absolute value not exceeding 2000. The next M lines contain prices ci, one number in each line. The prices are positive integers not exceeding 15 000.

Output

In the first line output 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, you should write one of them which is minimal according to the lexicographic order.

Sample

inputoutput
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
Problem Author: Dmitry Filimonenkov
Problem Source: Ural State University Internal Contest October'2000 Students Session
To submit the solution for this problem go to the Problem set: 1041. Nikifor