#include "bits/stdc++.h"
using namespace std;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2510&lang=jp
typedef long long ll;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N;
	while (cin >> N, N) {
		vector<pll> rw(N);
		for (int i = 0; i < N;i++)cin >> rw[i].first >> rw[i].second;
		sort(rw.begin(), rw.end());
		ll sum = 0;
		for (int i = 0; i < N - 1;i++)sum += rw[i].first;
		if (rw[N - 1].first <= sum) {
			ll ans = 0; ans = sum + rw[N - 1].first;
			for (int i = 0;i < N;i++) ans += rw[i].second;
			cout << ans << endl;
		}
		else {
			vector<vector<ll>> dp(N, vector<ll>(rw[N - 1].first - sum + 1, 0));
			dp[0][0] = 1;
			ll max_impress = 0;
			for (int i = 0; i < N-1;i++) {
				for (int t = 0; t <= rw[N - 1].first - sum;t++) {
					if (dp[i][t] != 1) continue;
					dp[i + 1][t] = dp[i][t];
					if (t + rw[i].second <= rw[N - 1].first - sum) {
						dp[i + 1][t + rw[i].second] = 1;
						max_impress = max(max_impress, t + rw[i].second);
					}
				}
			}
			ll ans = 0; ans = sum + rw[N - 1].first;
			for (int i = 0;i < N;i++) ans += rw[i].second;
			ans += (rw[N - 1].first - sum - max_impress);
			cout << ans << endl;
		}
	}
	return 0;
}