Emptying the Glasses

Mislav has $N$ glasses of unlimited volume, and every glass holds some water. He wants to drink all of the water, but he does not want to drink from more than $K$ glasses. The only thing he can do is pour all of the water from one glass into another glass.

The glasses are not all the same distance away from him, so the choice of glasses matters. Pouring the water from glass $i$ into glass $j$ costs $C_{ij}$ effort.

Find the smallest total effort needed to leave water in at most $K$ glasses.

The first line contains the integers $N$ and $K$ ($1 \le K \le N \le 20$).

Each of the next $N$ lines contains $N$ integers. The $j$-th number on the $i$-th line is $C_{ij}$ ($0 \le C_{ij} \le 100000$). $C_{ii} = 0$ holds for every $i$.

Print the minimum total effort on one line.

If at most $K$ glasses hold water from the start, no pouring is needed and the answer is 0.

Water may travel through several glasses. Mislav can pour glass $i$ into glass $j$, then later pour glass $j$ into glass $k$.