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

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的不知名学校的万里香的不知名餐饮公司吃了一顿
重新站了起来