#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
int n,a[N],f[N][N];
signed main(){
	cin>>n;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		f[i][i] = 0;
	}
	sort(a+1,a+n+1);
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r = l+len-1;
			f[l][r] = min(f[l+1][r]+a[r]-a[l],f[l][r-1]+a[r]-a[l]);
		}
	}
	cout<<f[1][n]<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
int a[20];
int f[1000005][20];
int e[25][25];
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		int x,y,z;
		cin>>x>>y>>z;
		e[x][y] = z;
	}
	for(int i=1;i<=n;i++){
		f[1<<(i-1)][i] = a[i];
	}
	for(int i=0;i<=(1<<n)-1;i++){
		for(int j=1;j<=n;j++){
			if((i&(1<<(j-1)))==0)continue;
			for(int k=1;k<=n;k++){
				if((i&(1<<(k-1)))==0 || k==j)continue;
				f[i][j] = max(f[i][j],f[i-(1<<(j-1))][k]+a[j]+e[k][j]);
			}
		}
	}
	int res = 0;
	for(int i=0;i<=(1<<n)-1;i++){
		if(__popcount(i)==m){
			for(int j=1;j<=n;j++){
				res = max(res,f[i][j]);
			}
		}
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
int T,n,x;
int v[55],c[55];
int f[50005];
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>x;
		for(int i=1;i<=n;i++){
			cin>>v[i]>>c[i];
		}
		memset(f,0x3f,sizeof(f));
		f[0] = 0;
		for(int i=1;i<=n;i++){
			for(int j=50000;j>=c[i];j--){
				if((i-1)*x>=f[j-c[i]]+v[i])
					f[j] = min(f[j],f[j-c[i]]+v[i]);
			}
		}
		for(int i=50000;i>=0;i--){
			if(f[i]<=(n-1)*x){
				cout<<i<<endl;
				break;
			}
		}
	}
	return 0;
}