#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 55, M = 3e6+5;
int a[N], b[N];

unordered_map<int, int> pre, suf;

int sa[1<<25], sb[1<<25];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    int t = n/2;
    int S = 0;
    for (int i = t; i < n; ++i) S += b[i];
    for (int i = 0; i < (1<<(n-t)); ++i) {
        if (i) {
        int cur = i & -i;
        sa[i] = sa[i^cur] + a[t+__builtin_ctz(cur)];
        sb[i] = sb[i^cur] + b[t+__builtin_ctz(cur)];
        }
        int K = sa[i]-S+sb[i];
        if (pre.find(K) == pre.end()) pre[K] = S-sb[i];
        else pre[K] = min(pre[K], S-sb[i]);
        if (suf.find(-K) == suf.end()) suf[-K] = sa[i];
        else suf[-K] = min(suf[-K], sa[i]);

    }
    int mn = INT_MAX;
    for (auto &[k, v] : pre) {
        mn = min(mn, v);
        v = mn;
    }
    mn = INT_MAX;
    for (auto &[k, v] : suf) {
        mn = min(mn, v);
        v = mn;
    }
    S = 0;
    int ans = INT_MAX;
    for (int i = 0; i < t; ++i) S += b[i];
    for (int i = 0; i < (1<<t); ++i) {
        if (i) {
        int cur = i & -i;
        sa[i] = sa[i^cur] + a[__builtin_ctz(cur)];
        sb[i] = sb[i^cur] + b[__builtin_ctz(cur)];
        }
        int A = sa[i], B = S - sb[i];
        auto it = pre.upper_bound(B-A);
        if (it != pre.begin()) ans = min(ans, B + prev(it)->second);
        it = suf.upper_bound(A-B);
        if (it != suf.begin()) ans = min(ans, A + prev(it)->second);
    }
    cout << ans << '\n';
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:31:16: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   31 |     for (auto &[k, v] : pre) {
      |                ^
answer.code:36:16: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   36 |     for (auto &[k, v] : suf) {
      |                ^
answer.code:50:23: error: ‘class std::unordered_map<int, int>’ has no member named ‘upper_bound’
   50 |         auto it = pre.upper_bound(B-A);
      |                       ^~~~~~~~~~~
answer.code:52:18: error: ‘class std::unordered_map<int, int>’ has no member named ‘upper_bound’
   52 |         it = suf.upper_bound(A-B);
      |                  ^~~~~~~~~~~