#include<bits/stdc++.h>
using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              ld;//%Lf
#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define ppb                 pop_back
#define in                  insert
#define sz(a)               int((a).size())
#define vi                  vector< int >
#define vll                 vector< ll >
#define pii                 pair<ll,ll>
#define YES                 cout << "YES\n"
#define NO                  cout << "NO\n"

#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define min_ele(v)          (*min_element(all(v)))
#define max_ele(v)          (*max_element(all(v)))
#define cnt_ele(v, x)       (count(all(v), x))
#define sum_ele(v)          (accumulate(all(v),0))
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
#define MAXP                1000006
#define MOD                 1e9+7//10000007 // For big mod
#define EPS                 1e-7

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}
vector<pair<ll,ll>>v;
bool cmp(pii x, pii y)
{
    return x.ss>y.ss;
}
int main()
{
    BITCH_FAST();
    #ifdef FLAME
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ll n, i, j;
    cin >> n;
    ll sum=0, ans;
    f1(n)
    {
        ll a, b;
        cin >> a >> b;
        v.pb({a,b});
        sum+=a;
    }
    ans=sum*2;
    sort(v.begin(), v.end(), cmp);
    f0(sz(v))
    {
        ll x, k;
        x=v[i].ff;
        k=v[i].ss;
        if(sum<=k)
            ;
        else
        {
            ll p=min(sum-k,x);
            ans-=p;
            sum-=p;
        }

    }
    cout << ans << endl;
    #ifdef FLAME
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

### Prompt

In Cpp, your task is to solve the following problem:

Lena is the most economical girl in Moscow. So, when her dad asks her to buy some food for a trip to the country, she goes to the best store — "PriceFixed". Here are some rules of that store:

  * The store has an infinite number of items of every product. 
  * All products have the same price: 2 rubles per item. 
  * For every product i there is a discount for experienced buyers: if you buy b_i items of products (of any type, not necessarily type i), then for all future purchases of the i-th product there is a 50\% discount (so you can buy an item of the i-th product for 1 ruble!). 



Lena needs to buy n products: she must purchase at least a_i items of the i-th product. Help Lena to calculate the minimum amount of money she needs to spend if she optimally chooses the order of purchasing. Note that if she wants, she can buy more items of some product than needed.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the number of products.

Each of next n lines contains a product description. Each description consists of two integers a_i and b_i (1 ≤ a_i ≤ 10^{14}, 1 ≤ b_i ≤ 10^{14}) — the required number of the i-th product and how many products you need to buy to get the discount on the i-th product. 

The sum of all a_i does not exceed 10^{14}.

Output

Output the minimum sum that Lena needs to make all purchases. 

Examples

Input


3
3 4
1 3
1 5


Output


8


Input


5
2 7
2 8
1 2
2 4
1 8


Output


12

Note

In the first example, Lena can purchase the products in the following way:

  1. one item of product 3 for 2 rubles, 
  2. one item of product 1 for 2 rubles, 
  3. one item of product 1 for 2 rubles, 
  4. one item of product 2 for 1 ruble (she can use the discount because 3 items are already purchased), 
  5. one item of product 1 for 1 ruble (she can use the discount because 4 items are already purchased). 



In total, she spends 8 rubles. It can be proved that it is impossible to spend less.

In the second example Lena can purchase the products in the following way:

  1. one item of product 1 for 2 rubles, 
  2. two items of product 2 for 2 rubles for each, 
  3. one item of product 5 for 2 rubles, 
  4. one item of product 3 for 1 ruble, 
  5. two items of product 4 for 1 ruble for each, 
  6. one item of product 1 for 1 ruble. 



In total, she spends 12 rubles.

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              ld;//%Lf
#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define ppb                 pop_back
#define in                  insert
#define sz(a)               int((a).size())
#define vi                  vector< int >
#define vll                 vector< ll >
#define pii                 pair<ll,ll>
#define YES                 cout << "YES\n"
#define NO                  cout << "NO\n"

#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define min_ele(v)          (*min_element(all(v)))
#define max_ele(v)          (*max_element(all(v)))
#define cnt_ele(v, x)       (count(all(v), x))
#define sum_ele(v)          (accumulate(all(v),0))
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
#define MAXP                1000006
#define MOD                 1e9+7//10000007 // For big mod
#define EPS                 1e-7

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}
vector<pair<ll,ll>>v;
bool cmp(pii x, pii y)
{
    return x.ss>y.ss;
}
int main()
{
    BITCH_FAST();
    #ifdef FLAME
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ll n, i, j;
    cin >> n;
    ll sum=0, ans;
    f1(n)
    {
        ll a, b;
        cin >> a >> b;
        v.pb({a,b});
        sum+=a;
    }
    ans=sum*2;
    sort(v.begin(), v.end(), cmp);
    f0(sz(v))
    {
        ll x, k;
        x=v[i].ff;
        k=v[i].ss;
        if(sum<=k)
            ;
        else
        {
            ll p=min(sum-k,x);
            ans-=p;
            sum-=p;
        }

    }
    cout << ans << endl;
    #ifdef FLAME
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}

```