Masala #5NRRVB41BZ

You are given m vectors in n-dimensional space. Additionally, you are aware of the costs associated with each vector. Your task is to select n linearly independent vectors with the minimum total cost.

The first line contains two integers m and n, where 3≤n≤50 and n≤m≤2000.

The following m lines contain vectors. All coordinates of the vectors are integers, with absolute values not exceeding 2000.

The next m lines contain numbers ci​, the cost of the i-th vector. The costs are positive integers, not exceeding 15000.

If it is not possible to select n linearly independent vectors, output 0. Otherwise, output the minimum sum of n linearly independent vectors.