题目描述

有 $N$ 个人正在排队，编号为 $1$ 到 $N$。

现在，需要将它们分成 $K$ 个小组，要求每个小组内的成员编号必须连续。

任意两个人只要待在一个小组，它们就会产生一些冲突。如果 $i$ 号与 $j$ 号待在一个小组，那么冲突值就是 $A_{i,j}$。

一个分组方案的总冲突值，就是所有两两小组成员的冲突值之和。

请问如何将为这些人分组，才能让总冲突值达到最小，输出这个最小的总冲突值。

输入格式

• 第一行：两个整数表示 $N$ 与 $K$。
• 第二行：$N-1$ 个整数表示 $A_{1,2},A_{1,3},\dots, A_{1,N}$
• 第三行：$N-2$ 个整数表示 $A_{2,3},A_{2,4},\dots, A_{2,N}$
• 其余行的输入格式以此类推。
• 第 $N$ 行：$1$ 个整数表示 $A_{N-1,N}$

输出格式

4 2
0 1 1 
1 1 
0

0

样例解释 1

前两个一组，后两个一组

数据范围

• 对于 $30\%$ 的数据，$1\leq K\leq N\leq 100$
• 对于 $60\%$ 的数据，$1\leq K\leq N\leq 1000$
• 对于 $100\%$ 的数据，$1\leq K\leq N\leq 3000$
• $1\leq K\leq 1000$
• $0\leq A_{i,j}<1000$

来源

改编自 CF321E Ciel and Gondolas