Problem Description

Mislav has $N$ glass cups, numbered from $1$ to $N$. Each cup contains some water. You need to make it so that only $K$ cups contain water by pouring water (pouring the water from one cup into another).

It is known that pouring the water from cup $i$ into cup $j$ costs $C_{i,j}$. Mislav wants to know the minimum total cost needed so that after pouring, only $K$ (or fewer) cups contain water.

Input Format

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

The next $N$ lines each contain $N$ non-negative integers $C_{i,j}$. The number in row $i$, column $j$ means the cost to pour water from cup $i$ to cup $j$. It is guaranteed that $C_{i,i}$ is always $0$.

Output Format

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

3 3
0 1 1
1 0 1
1 1 0 

0

3 2
0 1 1
1 0 1
1 1 0 

1

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 

5

Hint

Explanation for Sample 1

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

Explanation for Sample 2

Mislav needs to pour the water from any one cup into any other cup, so that only two cups contain water. The total cost is $1$.

Explanation for Sample 3

Mislav can pour water from cup $4$ into cup $3$, then pour the water in cup $3$ into cup $5$, and finally pour the water in cup $1$ into cup $5$. The total cost is $1+2+2=5$.

Constraints

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

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

Notes

Translated from COCI2016-2017 CONTEST #3 T3 Kroničan。

Translated by ChatGPT 5