该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

刘宝宝在科洛桑度假的时候，发现了成群结队的痞老板，痞老板们在排队等去三体的星际列车，一部星际列车可以承载无数多的痞老板，但是眼神尖锐的刘宝宝发现痞老板们之间都互相猜忌埋怨，因为他们都想独占 南方中学食堂食品秘方来毒死蟹老板。所以对于每一对痞老板，都有怨气值。只有在同一部车中的痞老板才会怨恨（眼不见为净）。因为要排队，所以一部车只能载一段连续的痞老板。
现在刘宝宝希望怨恨值的总和尽量的小，因为星际列车是刘宝宝公司的，刘宝宝不希望星际列车被破坏。因为刘宝宝说了我今天开不出金色传说DK就不打代码了，所以他让你来写这个代码。

Description

$n$只痞老板在乘星际列车，现在共有$k$辆星际列车可以运行（星际列车走了短时间不会回来，也就是要一次性分配所有痞老板）。一辆星际列车只能载一段连续的痞老板。

痞老板们互相有着深深的怨念，每一对痞老板之间有怨气值。第 $i$ 只痞老板与第 $j$ 只痞老板的怨气值记为$Y_{ij}$，且$Y_{ij}=Y_{ji}$，$Y_{ii}=0$ 。每辆星际列车载重不限，但是每一对在同辆星际列车中的痞老板都会产生怨气值。

输出最小怨气值之和 $Ans$ 。

Format

Input

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

接下来读入一个 $n$ 行 $n$ 列的矩阵。矩阵中第 $i$ 行 $j$ 列的元素表示$Y_{ij}$。当然这个矩阵是对称的。

Output

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

★注意：同辆星际列车中，痞老板 $i,j$ 之间的怨气只算一次！

Sample 1

Input

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

Output

7

样例说明：

编号为1，2，3的痞老板一辆车：怨气值和为3；

编号为4，5，6的痞老板一辆车：怨气值和为3；

编号为7，8的痞老板一辆车：怨气值和为1。

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

Sample 2

Input

5 1
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Output

10

Limitation

时空限制： $2s,256MB$

数据规模：

对于1-10点数据，$n \le 200$
对于11-17点数据，$n \le 1000$
对于所有数据，$n \le 4000$,$k \le 800$

猴急（Afterword）

被痞老板算计吃下了南方中学食堂饭菜的蟹老板晕厥在地

后来蟹老板来到一个叫作YaLi的不知名学校的万里香的不知名餐饮公司吃了一顿
重新站了起来