#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int N,length,maximum;
bool check[1100];

void func(){

	int read[N],write[N],read_sum = 0,write_sum = 0;

	for(int i = 0; i < N; i++){
		scanf("%d %d",&read[i],&write[i]);
		read_sum += read[i];
		write_sum += write[i];
	}

	sort(read,read+N,greater<int>());
	sort(write,write+N,greater<int>());

	if(N > 1 && read[0] >= read_sum-read[0]){

		length = read[0]-(read_sum-read[0]);

		if(write[N-1] <= length){

			check[0] = true;
			for(int i = 1; i <= length; i++)check[i] = false;
			check[write[N-1]] = true;
			maximum = write[N-1];

			for(int i = N-2; i >= 1; i--){
				if(write[i] > length)break;

				for(int k = length; k-write[i] >= 0; k--){
					if(check[k-write[i]] == true)check[k] = true;
				}
			}

			for(int k = maximum + 1; k <= length; k++){
				if(check[k]){
					maximum = k;
				}
			}

		}else{
			maximum = 0;
		}

		printf("%d\n",max(read_sum+write_sum,2*read[0]+write_sum-maximum));

	}else{
		if(N == 1){
			printf("%d\n",2*read[0]+write[0]);
		}else{
			printf("%d\n",read_sum+write_sum);
		}

	}

}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}