Emptying the Glasses

Time limit2sMemory limit32 MB

Summary

Given N glasses and pairwise pour costs, find the minimum effort to end with water in at most K glasses.

Level: Medium6 of 10
Topics: Dynamic programming, Graph, Bit manipulation, Shortest path
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

Print the minimum total effort on one line.

Hint

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$ .

Examples3

Example 1
Input
```
3 3
0 1 1
1 0 1
1 1 0
```
Expected output
```
0
```
Example 2
Input
```
3 2
0 1 1
1 0 1
1 1 0
```
Expected output
```
1
```

Example 3

Input

Expected output