小 Mislav 有 $N$ 个容量无限的水杯，每个水杯里都装有一些水。Mislav 想喝完所有的水，但他不想从超过 $K$ 个水杯中喝水。Mislav 可以对水杯进行的操作是：将一个水杯中的全部水倒入另一个水杯中。

不幸的是，对 Mislav 来说，选择哪个水杯是很重要的，因为并不是所有的水杯都离他一样远。更具体地说，将编号为 $i$ 的水杯中的水倒入编号为 $j$ 的水杯中所需的体力值为 $C_{ij}$。

请帮助 Mislav 找到一种倒水的顺序，使得将水集中到不超过 $K$ 个水杯中的总体力值消耗最小。

输入格式

输入的第一行包含两个整数 $N, K$ ($1 \le K \le N \le 20$)。

接下来的 $N$ 行，每行包含 $N$ 个整数 $C_{ij}$ ($0 \le C_{ij} \le 10^5$)。第 $i$ 行第 $j$ 列包含的值为 $C_{ij}$。保证所有的 $C_{ii}$ 都等于 0。

输出格式

输出 Mislav 达到目标所需的最小体力值。

子任务

在占总分 40 分的测试用例中，满足 $N \le 10$。

样例

输入样例 1

3 3
0 1 1
1 0 1
1 1 0

输出样例 1

0

说明 1

Mislav 不需要倒水，就可以从不超过 3 个水杯中喝水。

输入样例 2

3 2
0 1 1
1 0 1
1 1 0

输出样例 2

1

说明 2

Mislav 必须将恰好一个水杯（具体是哪个无所谓）中的水倒入另一个水杯中，这样就只剩下两个装有水的水杯。

输入样例 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

输出样例 3

5

说明 3

为了达到最小体力值 5，Mislav 可以将水从水杯 4 倒入水杯 3（消耗体力 1），然后从水杯 3 倒入水杯 5（消耗体力 2），最后从水杯 1 倒入水杯 5（消耗体力 2）。总共消耗的体力为 $1 + 2 + 2 = 5$。