 #include <bits/stdc++.h>
 using namespace std;
 #define ll long long
 #define ull unsigned long long
 #define ld long double
 #define vll std::vector<ll>
 #define pii pair<int,int>
 #define pll pair<ll,ll>
 #define vpll std::vector<pll>
 #define mll  std::map<ll, ll>
 #define sll set<ll>
 #define pq priority_queue<ll>
 #define pqmin priority_queue<ll,vll,greater<ll>> 
 #define umap unordered_map<int, int>
 #define letsgo ll test;cin>>test; while(test--)
 #define rep(i,a,n) for(ll i=a;i<n;i++)
 #define repd(i,a,n) for(ll i=a;i>n;i--)
 #define repm(i,m) for(auto i =m.begin();i!=m.end();i++)
 #define reps(i,m) for(auto i =m.begin();i!=m.end();i++)
 #define repmd(i,m) for(auto i =m.rbegin();i!=m.rend();i++)
 #define repsd(i,m) for(auto i =m.rbegin();i!=m.rend();i++)
 #define mp make_pair
 #define mt make_tuple
 #define pb push_back
 #define pob pop_back
 #define eb emplace_back
 #define all(v) (v).begin(), (v).end()
 #define sz(v) ((int)(v).size())
 #define len(a) ((int)(a).length())
 #define sqr(x) ((x) * (x))
 #define brk "\n"

 
  
 #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 
 const int mx = (int)2e5 + 1;  //   2*10^5
 const ll infl = 0x3f3f3f3f3f3f3f3fLL;
 const int infi = 0x3f3f3f3f;
 const ll mod=1e9 + 7;
 const int64_t INF = 1e17;
 
ll powm(ll a,ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
ll power(ll a,ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) ;
    a = (a * a) ;
    b >>= 1;
  }
  return res;
}
double nthRoot(ll A, ll N){
    double xPre = rand() % 10;
    double eps = 1e-3;
    double delX = INT_MAX;
    double xK;
    while (delX > eps)
    {
        xK = ((N - 1.0) * xPre +
              (double)A/pow(xPre, N-1)) / (double)N;
        delX = abs(xK - xPre);
        xPre = xK;
    }
 
    return xK;
}
ll divide(ll a,ll b) {
  return (a % mod) * powm(b, mod - 2) % mod;
}
ll mulm(ll a,ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
 
ll addm(ll a,ll b) {
  return (a % mod + b % mod) % mod;
}
inline int64_t mul(int64_t a, int64_t b){
  return (INF / a > b ? a * b : INF);
}
 
inline int64_t add(int64_t a, int64_t b){
  return (a + b >= INF ? INF : a + b);
}

bool isPrime(ll n){
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
}

ll gcd(ll a, ll b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
ll extgcd(ll a,ll b,ll& x,ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
ll totfun(ll n){
        ll ans = n;
        for(ll i=2;i*i<=n;i++){
            if(n%i==0){
                while(n%i==0)n/=i;
                ans-=ans/i;
            }
        }
        if(n>1)ans-=ans/n;
        return ans;
}

ll fact[mx];
ll nCr(ll n,ll r){
    if(r>n||r<0) return 0;
    ll z=fact[n];
    z=mul(z,powm(fact[n-r],mod-2));
    z=mul(z,powm(fact[r],mod-2));
    return z;
}

 /*
fact[0]=1;
rep(i,1,mx){
 fact[i]=mul(i,fact[i-1]);
}
*/

/*
 // segment tree 
struct item{
  ll pre,suf,mxs,sum; 
};
item st[4*mx];
ll a[mx];
 
item comb(item p1,item p2){
  item p;
  p.pre=max(p1.pre, p1.sum+p2.pre);
  p.suf=max(p2.suf, p2.sum+p1.suf);
  p.sum=p1.sum+p2.sum;
  p.mxs=max(max(p1.mxs,p2.mxs),p1.suf+p2.pre);
  return p;
}
 
void buildst(ll v,ll tl , ll tr){
  if(tl >=tr){
    st[v].pre = a[tl];
    st[v].suf= a[tl];
    st[v].mxs = a[tl];
    st[v].sum = a[tl]; 
  }
  else{
  ll tm = (tl+tr)/2;
  buildst(v*2,tl,tm);
  buildst(v*2+1,tm+1,tr);
  st[v] = comb(st[v*2],st[v*2+1]);
  }
}
item query(ll x,ll l,ll r,ll p,ll q){
    if(p>r||q<l) return {0,0,0,0};
    if(p<=l&&q>=r) return st[x];
    ll mid=(l+r)/2;
    item a=query(2*x,l,mid,p,q);
    item b=query(2*x+1,mid+1,r,p,q);
    return comb(a,b);
}
void upd(ll x,ll l,ll r,ll q){
    if(l==r){
        st[x]={max((ll)0,a[l]),max((ll)0,a[l]),max((ll)0,a[l]),a[l]};
        return;
    }
    ll mid=(l+r)/2;
    if(q<=mid) upd(2*x,l,mid,q);
    else upd(2*x+1,mid+1,r,q);
    st[x]=comb(st[2*x],st[2*x+1]);
}
*/
 

 /*matrix exponential
 ll n;
   ll d;
   cin>>n;
   ll ans[2]={0,1};
   ll a[2][2],tmp[2][2];
   a[0][0]=0;
   a[0][1]=1;
   a[1][0]=1;
   a[1][1]=1;
   while(n>0){
       if(n%2){
           d=ans[0];
           ans[0]=(d*a[0][0]+a[1][0]*ans[1])%mod;
           ans[1]=(d*a[0][1]+a[1][1]*ans[1])%mod;
       }
       tmp[0][0]=(a[0][0]*a[0][0]+a[0][1]*a[1][0]); 
       tmp[0][1]=(a[0][0]*a[0][1]+a[0][1]*a[1][1]); 
       tmp[1][0]=(a[1][0]*a[0][0]+a[1][1]*a[1][0]); 
       tmp[1][1]=(a[1][0]*a[0][1]+a[1][1]*a[1][1]); 
       rep(i,0,2){
           rep(j,0,2) a[i][j]=tmp[i][j]%mod;
       }
       n/=2;
   }
   cout<<ans[0];
 */
 bool cmpd(pll a,pll b){
   return a.second>b.second;
  }
 bool cmpa(pll a,pll b){
    return a.second<b.second;
  }
  /*
  vll primes;
  const ll mxprime = (ll)13e5;
  void sieveoferatosthenes(){   
    primes.pb(2);
    primes.pb(3);
    for(ll i=5;i<mxprime;i+=6){
        if(isPrime(i))primes.pb(i);
        if(isPrime(i+2))primes.pb(i+2);
    } 
  }
  */

 // #define sort(a) sort(a.begin(),a.end()) 
 vector<ll> g[mx];
 bool vis[mx];
 
 // LOOK FROM A DIFFERENT ANGLE
 // YOUR WAY IS NOT THE OPTIMAL WAY, THINKKKKK
 // CHECK SPECIAL CASES (0 1)
 // READ THE PROBLEM CAREFULLY
 // ALWAYS READ THE PROBLEM BEFORE THE FIRST SUBMISSION
 // DONT FALL FOR GIVEN TESTCASES
 // KIS BAAT KI JLDI HAI BHAI, THODA DHANG SE SOCH TO LE BHOSDIKE
 // EKDUM SHURU SE SOCHHH

 void solve(){
  ll n;cin>>n;
  vpll t;
  rep(i,0,n){
    ll a,b;cin>>a>>b;
    t.pb({a,b});
  }
  sort(all(t),cmpa);
ll s=0,e=t.size()-1;
ll price=0;
    ll cur=0;
    while(s<=e){
        if(cur<t[s].second){
            ll kitne= min(t[e].first,t[s].second-cur);
            price+=2*kitne;
            cur+=kitne;
            if(kitne<t[e].first){
                t[e].first-=kitne;
            }
            else e--;
        }
        else{
            price+=t[s].first;
            cur+=t[s].first;
            s++;
        }
    }
cout<<price<<brk;

 }
 
 int main(){
   fast_io;
   // letsgo
   solve();
   
   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;
 #define ll long long
 #define ull unsigned long long
 #define ld long double
 #define vll std::vector<ll>
 #define pii pair<int,int>
 #define pll pair<ll,ll>
 #define vpll std::vector<pll>
 #define mll  std::map<ll, ll>
 #define sll set<ll>
 #define pq priority_queue<ll>
 #define pqmin priority_queue<ll,vll,greater<ll>> 
 #define umap unordered_map<int, int>
 #define letsgo ll test;cin>>test; while(test--)
 #define rep(i,a,n) for(ll i=a;i<n;i++)
 #define repd(i,a,n) for(ll i=a;i>n;i--)
 #define repm(i,m) for(auto i =m.begin();i!=m.end();i++)
 #define reps(i,m) for(auto i =m.begin();i!=m.end();i++)
 #define repmd(i,m) for(auto i =m.rbegin();i!=m.rend();i++)
 #define repsd(i,m) for(auto i =m.rbegin();i!=m.rend();i++)
 #define mp make_pair
 #define mt make_tuple
 #define pb push_back
 #define pob pop_back
 #define eb emplace_back
 #define all(v) (v).begin(), (v).end()
 #define sz(v) ((int)(v).size())
 #define len(a) ((int)(a).length())
 #define sqr(x) ((x) * (x))
 #define brk "\n"

 
  
 #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 
 const int mx = (int)2e5 + 1;  //   2*10^5
 const ll infl = 0x3f3f3f3f3f3f3f3fLL;
 const int infi = 0x3f3f3f3f;
 const ll mod=1e9 + 7;
 const int64_t INF = 1e17;
 
ll powm(ll a,ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
ll power(ll a,ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) ;
    a = (a * a) ;
    b >>= 1;
  }
  return res;
}
double nthRoot(ll A, ll N){
    double xPre = rand() % 10;
    double eps = 1e-3;
    double delX = INT_MAX;
    double xK;
    while (delX > eps)
    {
        xK = ((N - 1.0) * xPre +
              (double)A/pow(xPre, N-1)) / (double)N;
        delX = abs(xK - xPre);
        xPre = xK;
    }
 
    return xK;
}
ll divide(ll a,ll b) {
  return (a % mod) * powm(b, mod - 2) % mod;
}
ll mulm(ll a,ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
 
ll addm(ll a,ll b) {
  return (a % mod + b % mod) % mod;
}
inline int64_t mul(int64_t a, int64_t b){
  return (INF / a > b ? a * b : INF);
}
 
inline int64_t add(int64_t a, int64_t b){
  return (a + b >= INF ? INF : a + b);
}

bool isPrime(ll n){
    if (n <= 1) 
        return false; 
    if (n <= 3) 
        return true; 
    if (n % 2 == 0 || n % 3 == 0) 
        return false; 
    for (ll i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
    return true; 
}

ll gcd(ll a, ll b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
ll extgcd(ll a,ll b,ll& x,ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
ll totfun(ll n){
        ll ans = n;
        for(ll i=2;i*i<=n;i++){
            if(n%i==0){
                while(n%i==0)n/=i;
                ans-=ans/i;
            }
        }
        if(n>1)ans-=ans/n;
        return ans;
}

ll fact[mx];
ll nCr(ll n,ll r){
    if(r>n||r<0) return 0;
    ll z=fact[n];
    z=mul(z,powm(fact[n-r],mod-2));
    z=mul(z,powm(fact[r],mod-2));
    return z;
}

 /*
fact[0]=1;
rep(i,1,mx){
 fact[i]=mul(i,fact[i-1]);
}
*/

/*
 // segment tree 
struct item{
  ll pre,suf,mxs,sum; 
};
item st[4*mx];
ll a[mx];
 
item comb(item p1,item p2){
  item p;
  p.pre=max(p1.pre, p1.sum+p2.pre);
  p.suf=max(p2.suf, p2.sum+p1.suf);
  p.sum=p1.sum+p2.sum;
  p.mxs=max(max(p1.mxs,p2.mxs),p1.suf+p2.pre);
  return p;
}
 
void buildst(ll v,ll tl , ll tr){
  if(tl >=tr){
    st[v].pre = a[tl];
    st[v].suf= a[tl];
    st[v].mxs = a[tl];
    st[v].sum = a[tl]; 
  }
  else{
  ll tm = (tl+tr)/2;
  buildst(v*2,tl,tm);
  buildst(v*2+1,tm+1,tr);
  st[v] = comb(st[v*2],st[v*2+1]);
  }
}
item query(ll x,ll l,ll r,ll p,ll q){
    if(p>r||q<l) return {0,0,0,0};
    if(p<=l&&q>=r) return st[x];
    ll mid=(l+r)/2;
    item a=query(2*x,l,mid,p,q);
    item b=query(2*x+1,mid+1,r,p,q);
    return comb(a,b);
}
void upd(ll x,ll l,ll r,ll q){
    if(l==r){
        st[x]={max((ll)0,a[l]),max((ll)0,a[l]),max((ll)0,a[l]),a[l]};
        return;
    }
    ll mid=(l+r)/2;
    if(q<=mid) upd(2*x,l,mid,q);
    else upd(2*x+1,mid+1,r,q);
    st[x]=comb(st[2*x],st[2*x+1]);
}
*/
 

 /*matrix exponential
 ll n;
   ll d;
   cin>>n;
   ll ans[2]={0,1};
   ll a[2][2],tmp[2][2];
   a[0][0]=0;
   a[0][1]=1;
   a[1][0]=1;
   a[1][1]=1;
   while(n>0){
       if(n%2){
           d=ans[0];
           ans[0]=(d*a[0][0]+a[1][0]*ans[1])%mod;
           ans[1]=(d*a[0][1]+a[1][1]*ans[1])%mod;
       }
       tmp[0][0]=(a[0][0]*a[0][0]+a[0][1]*a[1][0]); 
       tmp[0][1]=(a[0][0]*a[0][1]+a[0][1]*a[1][1]); 
       tmp[1][0]=(a[1][0]*a[0][0]+a[1][1]*a[1][0]); 
       tmp[1][1]=(a[1][0]*a[0][1]+a[1][1]*a[1][1]); 
       rep(i,0,2){
           rep(j,0,2) a[i][j]=tmp[i][j]%mod;
       }
       n/=2;
   }
   cout<<ans[0];
 */
 bool cmpd(pll a,pll b){
   return a.second>b.second;
  }
 bool cmpa(pll a,pll b){
    return a.second<b.second;
  }
  /*
  vll primes;
  const ll mxprime = (ll)13e5;
  void sieveoferatosthenes(){   
    primes.pb(2);
    primes.pb(3);
    for(ll i=5;i<mxprime;i+=6){
        if(isPrime(i))primes.pb(i);
        if(isPrime(i+2))primes.pb(i+2);
    } 
  }
  */

 // #define sort(a) sort(a.begin(),a.end()) 
 vector<ll> g[mx];
 bool vis[mx];
 
 // LOOK FROM A DIFFERENT ANGLE
 // YOUR WAY IS NOT THE OPTIMAL WAY, THINKKKKK
 // CHECK SPECIAL CASES (0 1)
 // READ THE PROBLEM CAREFULLY
 // ALWAYS READ THE PROBLEM BEFORE THE FIRST SUBMISSION
 // DONT FALL FOR GIVEN TESTCASES
 // KIS BAAT KI JLDI HAI BHAI, THODA DHANG SE SOCH TO LE BHOSDIKE
 // EKDUM SHURU SE SOCHHH

 void solve(){
  ll n;cin>>n;
  vpll t;
  rep(i,0,n){
    ll a,b;cin>>a>>b;
    t.pb({a,b});
  }
  sort(all(t),cmpa);
ll s=0,e=t.size()-1;
ll price=0;
    ll cur=0;
    while(s<=e){
        if(cur<t[s].second){
            ll kitne= min(t[e].first,t[s].second-cur);
            price+=2*kitne;
            cur+=kitne;
            if(kitne<t[e].first){
                t[e].first-=kitne;
            }
            else e--;
        }
        else{
            price+=t[s].first;
            cur+=t[s].first;
            s++;
        }
    }
cout<<price<<brk;

 }
 
 int main(){
   fast_io;
   // letsgo
   solve();
   
   return 0;
 }
 
```