0分求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
int dp[10000010];
map<int,int> mp;
int sum,cnt,r,c,t,n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while (t--){
		cin >> n;
		sum=0;
		cnt=0;
		memset(a,0,sizeof(a));
		memset(dp,0,sizeof(dp));
		mp.clear();
		for (int i=1;i<=n;i++){
			cin >> r >> c;
			mp[r]=max(mp[r],c);
		}
		for (auto it:mp){
			a[++cnt]=(it.first+it.second)*2;
			sum+=a[cnt];
		}
//		cout << sum << " " << cnt << endl;
		sort(a+1,a+cnt+1);
		for (int i=1;i<=cnt;i++){
			for (int j=a[i];j<=sum/2;j++){
				dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
			}
		}
//		for (int j=1;j<=sum/2;j++){
//			cout << dp[j] << " ";
//		}
		cout << max(sum-dp[sum/2],dp[sum/2]) << '\n';
	}
	return 0;
}