1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 int dp[1011][5011]; 7 int a[5011]; 8 int k,n; 9 int sqr(int x)10 {11     return x*x;12 }13 bool cmp(const int a,const int b)14 {15     return a>b;16 }17 18 int main()19 {20     int t;21     scanf("%d",&t);22     while(t--)23     {24         scanf("%d%d",&k,&n);25         memset(dp,0,sizeof(dp));26         memset(a,0,sizeof(a));27         for(int i=1; i<=n; i++)28         {29             scanf("%d",&a[i]);30         }31         sort(a+1,a+n+1,cmp);32         k=k+8;33         for(int i=1; i<=k; i++)34         {35             dp[i][i*3]=dp[i-1][i*3-2]+sqr(a[i*3-1]-a[i*3]);36             for(int j=i*3+1; j<=n; j++)37             {38                 dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+sqr(a[j-1]-a[j]));39             }40         }41         printf("%d\n",dp[k][n]);42     }43     return 0;44 }