#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;
const int MAX=2001;
int s[MAX][MAX/2+1];//表示前i个物品搬j对物品的最小疲劳度.
int a[MAX];
int main(){
int n,k;
while(cin>>n>>k){
for(int i=0;i<n;++i){
cin>>a[i];
}
sort(a,a+n);//对物品重量进行排序
for(int j=1;j<=k;++j){
for(int i=1;i<=n;++i){
if(2*j<=i){
//如果前i个物品能搬j对物品
s[i][j]=min(s[i-2][j-1]+(a[i-1]-a[i-2])*(a[i-1]-a[i-2]),s[i-1][j]);
}
else s[i][j]=INF;//无法搬j对物品就疲劳度设为无穷大
}
}
cout<<s[n][k]<<endl;
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1421