问题 3031 --筷子(stick)

3031: 筷子(stick)

时间限制: 1 Sec  内存限制: 128 MB
提交: 11  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

中国人吃饭必须要用筷子。C先生与常人不同,他的一副筷子有3只,一对再加上一根比较长的,用来穿比较大的食物。两只较短的筷子的长度应该尽可能接近,但是最长的那根的长度是无所谓的。如果一副筷子的长度分别是A,B,C(A<=B<=C),则用(A-B)2的值表示这副筷子的质量,显然这个值越小,质量越高。

       C先生邀请了K个朋友去吃饭,而且他要为每个人准备一副这种特殊的筷子。C先生的家里有8个人,因此你总共必须准备K+8副筷子。不过C先生发现他的筷子有各种各样不同的长度,他必须找到一种办法搭配好K+8副筷子,使得这些筷子的质量值之和最小。

输入

第一行有一个整数T,表示文件中共有T组测试数据。T的值不超过20。每一组测试数据的第一行是两个整数KN(0<=K<=1000, 3K+24<=N<=5000)K是邀请朋友的人数,NC先生家里储备的筷子总根数。接下来的一行有N个正整数,表示这N根筷子的长度;这N个数是从小到大给出的,并且每一根筷子的长度值不超过32000

输出

对于每一组输入数据,输出单独一行,表示最小的质量值之和。你的答案应当写到stick.out中。

样例输入

1
1 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164

样例输出

23

提示


对于这个例子,一种可行的方案是:



8,10,16;
19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139;
157,157,160

来源

 

[提交][状态]