贞鱼

内存限制：162 MiB 时间限制：3 Sec

众所周知，贞鱼是一种高智商水生动物。不过他们到了陆地上智商会减半。

这不？他们遇到了大麻烦！

n只贞鱼到陆地上乘车，现在有k辆汽车可以租用。

由于贞鱼们并不能在陆地上自由行走，一辆车只能载一段连续的贞鱼。

贞鱼们互相有着深深的怨念，每一对贞鱼之间有怨气值。

第i只贞鱼与第j只贞鱼的怨气值记为Y_ij，且Y_ij=Y_ji，Y_ii=0。

每辆车载重不限，但是每一对在同辆车中的贞鱼都会产生怨气值。

当然,超级贞鱼zzp长者希望怨气值的总和最小。

不过他智商已经减半,想不出分配方案。

他现在找到了你,请你帮助他分配贞鱼们,并输出最小怨气值之和ans。

第一行两个整数:n,k。

接下来读入一个n行n列的矩阵。矩阵中第i行j列的元素表示Y_ij。

当然这个矩阵是对称的。

一个整数ans，表示：最小的怨气值之和

★注意：同辆车中，贞鱼i,j之间的怨气只算一次！

1 ≤ n ≤4000 ，1 ≤ k ≤min(n , 800) , 0 ≤ Yij≤10


			8 3

0 1 1 1 1 1 1 1

1 0 1 1 1 1 1 1

1 1 0 1 1 1 1 1

1 1 1 0 1 1 1 1

1 1 1 1 0 1 1 1

1 1 1 1 1 0 1 1

1 1 1 1 1 1 0 1

1 1 1 1 1 1 1 0


			7

编号为1，2，3的贞鱼一辆车：怨气值和为3；

编号为4，5，6的贞鱼一辆车：怨气值和为3；

编号为7，8的贞鱼一辆车：怨气值和为1。

最小怨气值总和为 3 + 3 + 1 = 7 。

#5311. 贞鱼