题目描述

Mislav 有 $N$ 个玻璃杯，从 $1\sim N$ 编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子），使这些杯子中只有 $K$ 个有水。

已知将第 $i$ 号玻璃杯中的水倒入第 $j$ 号，需要消耗 $C_{i,j}$ 的代价。Mislav 想知道，经过倒水后满足只有 $K$ 个（或更少）玻璃杯中有水时，消耗的代价总和的最小值。

输入格式

第一行包含两个正整数，$N,K$。

接下来 $N$ 行，每行包含 $N$ 个非负整数 $C_{i,j}$。第 $i$ 行 $j$ 列的数表示从玻璃杯 $i$ 倒水到玻璃杯 $j$ 需要付出的代价。保证 $C_{i,i}$ 一定是 $0$。

输出格式

输出 Mislav 达成目标需要付出的最小代价和。

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

提示

样例 1 解释

Mislav 不需要倒水。代价和是 $0$。

样例 2 解释

Mislav 需要将任意一个玻璃杯中的水倒入任何其他玻璃杯中，使其满足只有两个玻璃杯中有水。代价和为 $1$。

样例 3 解释

Mislav 可以将水从玻璃杯 $4$ 倒入玻璃杯 $3$，然后将玻璃杯 $3$ 中的水倒入玻璃杯 $5$，最后将玻璃杯 $1$ 中的水倒入玻璃杯 $5$。总共付出代价和为 $1+2+2=5$。

数据规模与约定

对于 $40\%$ 的数据，满足 $N\le 10$。

对于 $100\%$ 的数据，满足 $1\le K\le N\le 20,C_{i,j}\le10^5$

说明

题目译自 COCI2016-2017 CONTEST #3 T3 Kroničan。