P6883 [COCI 2016/2017 #3] Kroničan

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.

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 the minimum total cost Mislav needs to pay to achieve the goal.

#### 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #3](https://hsin.hr/coci/archive/2016_2017/contest3_tasks.pdf) _T3 Kroničan_**。 Translated by ChatGPT 5