#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<queue>#define add 100#define maxn 120#define inf 2139062143using namespace std;int x[maxn],y[maxn];int N;int dp[maxn][250];int main(){ int i,j; int T; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%d %d",&x[i],&y[i]); } memset(dp,0x7f,sizeof(dp)); dp[0][100]=0; for(i=0;i<N;i++) { for(j=0;j<=200;j++) { if(dp[i][j]==inf) continue; if(j>=100) { dp[i+1][x[i+1]+add]=min(dp[i+1][x[i+1]+add],dp[i][j]+x[i+1]); dp[i+1][j-y[i+1]]=min(dp[i+1][j-y[i+1]],dp[i][j]+max(0,y[i+1]-(j-add))); } else { dp[i+1][-y[i+1]+add]=min(dp[i+1][-y[i+1]+add],dp[i][j]+y[i+1]); dp[i+1][j+x[i+1]]=min(dp[i+1][j+x[i+1]],dp[i][j]+max(0,x[i+1]-(add-j))); } } } int ans=inf; for(i=0;i<=200;i++) { ans=min(ans,dp[N][i]); } printf("%dn",ans); } return 0;}
