#include<iostream>
#include<algorithm>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int a[5005];
int dp[1001][5005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
bool cmp(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
return a > b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int getMin(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(a < b)
return a;
else
return b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int text;
cin>>text;
while(text--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int k,n;
int i,j;
cin>>k>>n;
for(i = 1;i <= n; i++ )
cin>>a[i];
k = k+8;
sort(a+1,a+n+1,cmp);
memset(dp,0,sizeof(dp));
for(i = 1;i <= k;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][3*i] = dp[i-1][3*i-2] + (a[i*3]-a[i*3-1])*(a[i*3]-a[i*3-1]);
for(j = 3*i+1 ; j <= n ;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
dp[i][j] = getMin(dp[i][j-1],dp[i-1][j-2] + (a[j]-a[j-1])*(a[j]-a[j-1]));
}
}
cout<<dp[k][n]<<endl;
}
return 0;
}