stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#define ll long long

#define int ll

#define lowbit(a) a&(-a)

using namespace std;



inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}

	return f*sum;

}



const int N=200000;

const int M=100000;

int n,m,a[N+5];

ll t[N+5],c[N+5],tem;



inline void add(int x){for(;x<=N;x+=lowbit(x)) t[x]++;}



inline ll ask(int x){ll ret=0;for(;x;x-=lowbit(x)) ret+=t[x];return ret;}



inline int check(int x){

	ll cnt=0;

	memset(t,0,sizeof(t));

	for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]<=x? 1:-1);

	add(1+M);

	for(int i=1;i<=n;i++){

		cnt+=ask(c[i]+M);

		add(c[i]+1+M);

	}

	return cnt>tem;

}



signed main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read();

	ll l=0,r=0;

	for(int i=1;i<=n;i++) r=max(r,(ll)a[i]);

	ll ans=r;

	tem=n*(n+1)/2;tem/=2;

	while(l<=r){

	ll mid=(l+r)>>1;

	if(check(mid)) ans=min(ans,mid),r=mid-1;

	else l=mid+1;

}

	printf("%lld\n",ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.4784896180434508x):
#include<bits/stdc++.h>



using namespace std;



#define int long long

int const maxn = 1e5 + 5;

int a[maxn], b[maxn], c[maxn], pref[maxn], f[2 * maxn];



inline void add(int x) {

    while (x < 2 * maxn) {

        f[x]++;

        x = (x|(x + 1));

    }

}



inline int get(int x) {

    int ans = 0;

    while (x > 0) {

        ans += f[x];

        x = (x&(x + 1)) - 1;

    }

    return ans;

}



main() {

#ifdef HOME

    freopen("input.txt", "r", stdin);

#endif // HOME

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int n;

    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) b[i] = a[i];

    sort(b + 1, b + n + 1);

    int lef = 0, righ = n;

    int sum = 0;

    for (int i = 1; i <= n; ++i) sum += (n - i + 1);

    while (righ - lef > 1) {

        int mid = (righ + lef) / 2;

        for (int j = 1; j <= n; ++j) {

            if (a[j] <= b[mid]) c[j] = 1;

            else c[j] = -1;

            pref[j] = pref[j - 1] + c[j];

        }

        int cnt = 0;

        for (int i = 0; i < 2 * maxn; ++i) f[i] = 0;

        add(maxn + 1);

        for (int j = 1; j <= n; ++j) {

            cnt += get(pref[j] + maxn);

            add(pref[j] + 1 + maxn);

        }

        if (cnt >= (sum + 2) / 2) righ = mid;

        else lef = mid;

    }

    cout << b[righ] << '\n';

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#define ll long long

#define int ll

#define lowbit(a) a&(-a)

using namespace std;



inline int read(){

	int sum=0,f=1;char c=getchar();

	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}

	return f*sum;

}



const int N=200000;

const int M=100000;

int n,m,a[N+5];

ll t[N+5],c[N+5],tem;



inline void add(int x){for(;x<=N;x+=lowbit(x)) t[x]++;}



inline ll ask(int x){ll ret=0;for(;x;x-=lowbit(x)) ret+=t[x];return ret;}



inline int check(int x){

	ll cnt=0;

	memset(t,0,sizeof(t));

	for(int i=1;i<=n;i++) c[i]=c[i-1]+(a[i]<=x? 1:-1);

	add(1+M);

	for(int i=1;i<=n;i++){

		cnt+=ask(c[i]+M);

		add(c[i]+1+M);

	}

	return cnt>tem;

}



signed main(){

	n=read();

	for(int i=1;i<=n;i++) a[i]=read();

	ll l=0,r=0;

	for(int i=1;i<=n;i++) r=max(r,(ll)a[i]);

	ll ans=r;

	tem=n*(n+1)/2;tem/=2;

	while(l<=r){

	ll mid=(l+r)>>1;

	if(check(mid)) ans=min(ans,mid),r=mid-1;

	else l=mid+1;

}

	printf("%lld\n",ans);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.485131855257392x):
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<queue>

#include<ctime>

#include<cassert>

#include<complex>

#include<string>

#include<cstring>

#include<chrono>

#include<random>

#include<bitset>

#include<iomanip>



#define fi first

#define se second

#define mp make_pair

#define eb emplace_back

#define all(v) v.begin(), v.end()

#define sz(v) (int) v.size()



using namespace std;



mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair<int, int> pii;



const int MAX_N = 1e5 + 5;



int n, a[MAX_N];

int pref[MAX_N], fenw[MAX_N * 2];



void update(int pos, int delta) {

	for (int i = pos; i <= 2 * n; i |= (i + 1)) {

		fenw[i] += delta;

	}

}



int get(int r) {

	int res = 0;

	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {

		res += fenw[i];

	}

	return res;

}



bool check(int m) {

	fill(fenw, fenw + 2 * n + 1, 0);

	for (int i = 1; i <= n; ++i) {

		pref[i] = pref[i - 1] + (a[i] >= m) - (a[i] < m);

	}

	update(n, 1);

	ll cnt = 0;

	for (int i = 1; i <= n; ++i) {

		cnt += get(pref[i] + n);

		update(pref[i] + n, 1);

	}

	return cnt >= (1ll * n * (n + 1) / 2 + 1) / 2;

}



signed main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin >> n;

	vector<int> diff;

	for (int i = 1; i <= n; ++i) {

		cin >> a[i];

		diff.eb(a[i]);

	}

	sort(all(diff));

	diff.resize(unique(all(diff)) - diff.begin());

	int lef = 0, rig = sz(diff);

	while (lef + 1 < rig) {

		int mid = (lef + rig) / 2;

		if (check(diff[mid])) {

			lef = mid;

		} else {

			rig = mid;

		}

	}

	cout << diff[lef] << "\n";

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

 



 

int main(){

 

	int n; 

	while(scanf("%d",&n),n){



		vector<pair<int,int> > rw(n);

		int sum_r=0,sum_w=0;

		for(int i=0;i<n;i++){

			cin>>rw[i].first>>rw[i].second;

			sum_r+=rw[i].first;

			sum_w+=rw[i].second;

		}

		sort(rw.begin(),rw.end(),greater< pair<int,int> >());



		int r0=rw[0].first;

		int r=sum_r-r0;



		if(r0 <= r){

			cout<<sum_r+sum_w<<endl;

		}else{



			int res=2*rw[0].first;

			vector<vector<bool> > dp(1001,vector<bool>(1000,false));



			//r0-r???w?????°??????

			//dp[pos][sum]



			dp[1][0]=true;

			for(int i=1;i<n;i++){

				for(int j=0;j<=1000;j++){

					if(dp[i][j]){

						dp[i+1][j]=true; //??°?????????

						if(j+rw[i].second<=10000)

							dp[i+1][j+rw[i].second]=true; //??°??????

					}

				}

			}



			int opt=0;

			for(int i=1;i<=r0-r;i++){

				if(dp[n][i]) opt=i;

			}



			res+=sum_w-opt;

			cout<<res<<endl;







		}

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.649214104436924x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<1000;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<1000)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

  

 

  

int main(){

  

    int n; 

    while(scanf("%d",&n),n){

 

        vector<pair<int,int> > rw(n);

        int sum_r=0,sum_w=0;

        for(int i=0;i<n;i++){

            cin>>rw[i].first>>rw[i].second;

            sum_r+=rw[i].first;

            sum_w+=rw[i].second;

        }

        sort(rw.begin(),rw.end(),greater< pair<int,int> >());

 

        int r0=rw[0].first;

        int r=sum_r-r0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

 

            int res=2*rw[0].first;

            vector<vector<bool> > dp(1001,vector<bool>(1000,false));

 

            dp[1][0]=true;

            for(int i=1;i<n;i++){

                for(int j=0;j<=1000;j++){

                    if(dp[i][j]){

                        dp[i+1][j]=true; 

                        if(j+rw[i].second<=1000)

                            dp[i+1][j+rw[i].second]=true; 

                    }

                }

            }

 

            int opt=0;

            for(int i=1;i<=r0-r;i++){

                if(dp[n][i]) opt=i;

            }

 

            res+=sum_w-opt;

            cout<<res<<endl;

 

 

 

        }

         

         

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.649214104436924x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<1000;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<1000)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool dp[1001][1000]={};

            dp[0][0]=true;

            for(int i=0;i<n;i++){

                for(int j=0;j<1000;j++){

                    if(dp[i][j]){

                        dp[i+1][j]=true; 

                        if(j+w[i]<1000)

                            dp[i+1][j+w[i]]=true; 

                    }

                }

            }

  

            int opt=r0-r;

            while(!dp[n][opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}

// Faster C++ solution for the same problem (measured speedup: 2.1919441895912986x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<1000;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<1000)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	bool dp[1001][1000]={};

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			fill(&dp[0][0],&dp[1001][0],false);

            dp[0][0]=true;

            for(int i=0;i<n;i++){

                for(int j=0;j<1000;j++){

                    if(dp[i][j]){

                        dp[i+1][j]=true; 

                        if(j+w[i]<1000)

                            dp[i+1][j+w[i]]=true; 

                    }

                }

            }

  

            int opt=r0-r;

            while(!dp[n][opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}

// Faster C++ solution for the same problem (measured speedup: 2.3316681826324763x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<1000;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<1000)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

 



 

int main(){

 

	int n; 

	while(scanf("%d",&n),n){



		vector<pair<int,int> > rw(n);

		int sum_r=0,sum_w=0;

		for(int i=0;i<n;i++){

			cin>>rw[i].first>>rw[i].second;

			sum_r+=rw[i].first;

			sum_w+=rw[i].second;

		}

		sort(rw.begin(),rw.end(),greater< pair<int,int> >());



		int r0=rw[0].first;

		int r=sum_r-r0;



		if(r0 <= r){

			cout<<sum_r+sum_w<<endl;

		}else{



			int res=2*rw[0].first;

			vector<vector<bool> > dp(1001,vector<bool>(1000,false));



			//r0-r???w?????°??????

			//dp[pos][sum]



			dp[1][0]=true;

			for(int i=1;i<n;i++){

				for(int j=0;j<=1000;j++){

					if(dp[i][j]){

						dp[i+1][j]=true; //??°?????????

						if(j+rw[i].second<=10000)

							dp[i+1][j+rw[i].second]=true; //??°??????

					}

				}

			}



			int opt=0;

			for(int i=1;i<=r0-r;i++){

				if(dp[n][i]) opt=i;

			}



			res+=sum_w-opt;

			cout<<res<<endl;







		}

		

		

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6590722570130945x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<=r0-r;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<=r0-r)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

  

 

  

int main(){

  

    int n; 

    while(scanf("%d",&n),n){

 

        vector<pair<int,int> > rw(n);

        int sum_r=0,sum_w=0;

        for(int i=0;i<n;i++){

            cin>>rw[i].first>>rw[i].second;

            sum_r+=rw[i].first;

            sum_w+=rw[i].second;

        }

        sort(rw.begin(),rw.end(),greater< pair<int,int> >());

 

        int r0=rw[0].first;

        int r=sum_r-r0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

 

            int res=2*rw[0].first;

            vector<vector<bool> > dp(1001,vector<bool>(1000,false));

 

            dp[1][0]=true;

            for(int i=1;i<n;i++){

                for(int j=0;j<=1000;j++){

                    if(dp[i][j]){

                        dp[i+1][j]=true; 

                        if(j+rw[i].second<=1000)

                            dp[i+1][j+rw[i].second]=true; 

                    }

                }

            }

 

            int opt=0;

            for(int i=1;i<=r0-r;i++){

                if(dp[n][i]) opt=i;

            }

 

            res+=sum_w-opt;

            cout<<res<<endl;

 

 

 

        }

         

         

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.6590722570130945x):
#include <iostream>

#include <string>

#include <vector>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cstdio>

#include <functional>

#include <set>

#include <queue>

#include <cctype>

#include <climits>

#include <stack>

using namespace std;

   

  

   

int main(){

   

    int n; 

    int r[1000],w[1000];

    int sum_r=0,sum_w=0,idx=0;

	

    while(scanf("%d",&n),n){

         

        sum_r=sum_w=idx=0;

        for(int i=0;i<n;i++){

            scanf("%d %d",&r[i],&w[i]);

            sum_r+=r[i];

            sum_w+=w[i];

            if(r[idx]<r[i]) idx=i;

        }

  

        int r0=r[idx],r=sum_r-r0;

        w[idx]=0;

 

        if(r0 <= r){

            cout<<sum_r+sum_w<<endl;

        }else{

  

            int res=2*r0;

            //vector<vector<bool> > dp(1001,vector<bool>(1000,false));

  

			bool cur[1001]={};

            cur[0]=true;

            for(int i=0;i<n;i++){

				bool next[1001]={};

                for(int j=0;j<=r0-r;j++){

                    if(cur[j]){

                        next[j]=true; 

                        if(j+w[i]<=r0-r)

                            next[j+w[i]]=true; 

                    }

                }

				swap(cur,next);

            }

  

            int opt=r0-r;

            while(!cur[opt]) opt--;

  

            res+=sum_w-opt;

            printf("%d\n",res);

  

  

  

        }

          

          

    }

}