← 返回题目列表

Codeforces · 321/E

E. Ciel 和贡多拉

中文机器翻译题面 查看原题

Fox Ciel 在游乐园里。而现在她正在摩天轮前排队。队列中有 n 个人(或者更准确地说是狐狸):我们使用第一个人来引用队列头部的一个人,使用第 n 个人来引用队列中最后一个人。

将会有k个吊船,我们分配吊船的方式如下所示:

- 当第一艘贡多拉到来时,队列前面的 q1 个人进入贡多拉。
- 然后当第二艘吊船到来时,剩下队列前面的 q2 人进入吊船。    ...
- 剩下的 qk 个人进入最后一个(第 k 个)吊舱。

请注意,q1、q2、...、qk 必须为正数。从语句中可以得到 $$\sum_{i=1}^{k} q_i = n$$ 且 qi > 0。

你知道,人们不想和陌生人一起呆在贡多拉里,所以你的任务就是找到一个最优的分配方式(即找到一个最优序列q)来让人们开心。对于每一对人 i 和 j,都存在一个值 uij 表示陌生程度。您可以假设对于所有 i、j (1 ≤ i, j ≤ n),uij = uji;对于所有 i (1 ≤ i ≤ n),假设 uii = 0。那么贡多拉的陌生值就是进入贡多拉的任何一对人之间的不熟悉程度的总和。

总陌生值是所有吊舱的陌生值之和。帮助 Fox Ciel 找到某些最佳分配的最小可能总陌生值。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 4000 and 1 ≤ k ≤ min(n, 800)) — 队列中的人数和缆车的数量。以下 n 行中的每一行包含 n 个整数 — 矩阵 u,(0 ≤ uij ≤ 9,uij = uji 且 uii = 0)。

请使用快速输入法(例如,请使用 BufferedReader 而不是 Scanner for Java)。

输出

打印一个整数——可能的最小总陌生值。

示例

输入 #1

5 2
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0

输出 #1

0

输入 #2

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

输出 #2

7

输入 #3

3 2
0 2 0
2 0 3
0 3 0

输出 #3

2

注意

在第一个例子中,我们可以这样分配人员:{1, 2} 进入一个缆车,{3, 4, 5} 进入另一个缆车。

在第二个示例中,最佳解决方案是:{1, 2, 3} | {4,5,6}| {7, 8}。