OpenJudge

K:雪风酱是不会沉的!

总时间限制:
3000ms
内存限制:
65536kB
描述

    提督又派雪风出击了。出击海域有N个点,每个点拥有一个攻略难度值D,雪风希望将这N个点任意分为M组分别攻略(M < N),每组包含至少一个点,每个点只能被一个组包含。每组中难度最大和最小值差的平方为该组的难度值。现在雪风想知道,出击海域的所有组的难度值之和最小是多少。

输入
首先输入正整数T,表示测试数据的组数。每组数据第一行输入N和M,表示出击海域的点数和雪风想要分组的数量。随后的一行包含N个数,表示每个点的攻略难度。

数据范围:
1≤T≤20
1≤N≤10000
1≤M≤5000 且 M0≤D_i≤9000
输出
对于每组测试数据,输出一行“Case #x: answer”,其中x是测试数据的组数,answer表示海域最小的难度值。
样例输入
2
3 2
1 2 4
4 2
4 7 10 1
样例输出
Case #1: 1
Case #2: 18
来源
NWPU
全局题号
12540
添加于
2016-12-24
提交次数
2
尝试人数
1
通过人数
1