#944. stong9070奇遇记之搬寝室

stong9070奇遇记之搬寝室

背景

stong9070是三国时代M国的一个谋士,某天他在落凤坡发现了一块黑黑的石头(远古陨石),这个石头能量非常强大,瞬间stong9070就穿越到了30003年。在寻找回三国时代的路上他偶然遇到了一个学生DVE,DVE很像他在三国时的一个好友HOKE,想起了和HOKE在一起的学生生活,不自觉地跟着DVE去了学校,学校正直新学期开学。开学非常重要的事情就是搬寝室。

题目描述

搬寝室是很累的,stong9070深有体会.时间追述到1997年9月1号,那天stong9070迫于无奈要从27号楼搬到3号楼,因为2号要封楼了.看着寝室里的nn件物品,stong9070开始发呆,因为nn是一个小于2000的整数,实在是太多了,于是stong9070决定随便搬2 * kk件过去就行了.但还是会很累,因为2 * kk也不小,是一个不大于nn的整数.

幸运的是stong9070根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,stong9070每次搬两件东西,左手一件右手一件).例如stong9070左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(63)2=9(6-3)^2 = 9.现在可怜的stong9070希望知道搬完这2 * kk件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧。

输入格式

每组输入数据有两行,第一行有两个数n,kn,k.第二行有nn个整数分别表示n件物品的重量(重量是一个小于2152^{15}的正整数).

输出格式

对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.

样例

5 1
18467 6334 26500 19169 15724 
7 1
29358 26962 24464 5705 28145 23281 16827 
492804
1399489

数据范围

22kn<20002 \leqslant 2*k \leqslant n<2000