Problem Description

Mislav has $N$ glass cups numbered from $1$ to $N$, each containing a certain amount of water. You need to transfer water (by pouring water from one cup to another) so that only $K$ cups contain water.

It is known that transferring water from cup $i$ to cup $j$ incurs a cost of $C_{i,j}$. Mislav wants to know the minimum total cost required to achieve the goal of having only $K$ (or fewer) cups with water.

Input Format

The first line contains two positive integers, $N$ and $K$.

The next $N$ lines each contain $N$ non-negative integers $C_{i,j}$. The number at the $i$-th row and $j$-th column represents the cost of transferring water from cup $i$ to cup $j$. It is guaranteed that $C_{i,i}$ is always $0$.

Output Format

Output the minimum total cost that Mislav needs to pay to achieve the goal.

Sample Input and Output

Input Sample #1

3 3
0 1 1
1 0 1
1 1 0

Output Sample #1

0

Input Sample #2

3 2
0 1 1
1 0 1
1 1 0

Output Sample #2

1

Input Sample #3

5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0

Output Sample #3

5

Notes

Sample 1 Explanation

Mislav does not need to transfer any water. The total cost is $0$.

Sample 2 Explanation

Mislav needs to transfer water from any one cup to any other cup to ensure only two cups contain water. The total cost is $1$.

Sample 3 Explanation

Mislav can transfer water from cup $4$ to cup $3$, then from cup $3$ to cup $5$, and finally from cup $1$ to cup $5$. The total cost is $1 + 2 + 2 = 5$.

Data Size and Constraints

For $40\%$ of the data, $N \le 10$.

For $100\%$ of the data, $1 \le K \le N \le 20$, and $C_{i,j} \le 10^5$.

Notes

This problem is translated from COCI2016-2017 CONTEST #3 T3 Kroničan.

见题面 Input 部分

见题面 Output 部分