#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define fi first #define se second #define mk make_pair using namespace std; const int N=1e5+10,MS=5e6; pii a[N]; int n; int f[N][3][3][4]; void cmn(int &a,int b){if(b<a) a=b;} void slv(){ memset(f,0x3f,sizeof(f)); f[0][0][0][1]=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].se>>a[i].fi; sort(a+1,a+n+1,greater<pii>()); for(int i=1;i<=n;i++){ for(int x=2;x>=0;x--){ for(int y=2;y>=0;y--){ for(int z=0;z<=3;z++){ //cout<<i<<' '<<x<<' '<<y<<' '<<z<<' '<<f[i-1][x][y][z]<<endl; cmn(f[i-1][x][y][min(z+2,2)],f[i-1][x][y][z]+3); cmn(f[i-1][x][y][min(z+1,2)],f[i-1][x][y][z]+3); cmn(f[i][x][y][min(z+1,2)],f[i-1][x][y][z]+a[i].fi*a[i].se+3-a[i].se); //add boat (w,w,w),(w,w,-),(w,w,v) if(a[i].se==1){ cmn(f[i][min(x+1,2)][y][z],f[i-1][x][y][z]+a[i].fi+2); //add boat (w,v1,-) if(x) cmn(f[i][x-1][y][z],f[i-1][x][y][z]); if(y) cmn(f[i][x][y-1][z],f[i-1][x][y][z]); //insert ()<-v1 if(z) cmn(f[i][min(x+2,2)][y][z-1],f[i-1][x][y][z]+a[i].fi+2); }else{ cmn(f[i][x][min(y+1,2)][z],f[i-1][x][y][z]+2*a[i].fi+1); //add boat (w,v2,-) if(x) cmn(f[i][x-1][y][z],f[i-1][x][y][z]+a[i].fi-1); if(y) cmn(f[i][x][y-1][z],f[i-1][x][y][z]); if(x>1) cmn(f[i][x-2][min(y+1,2)][z],f[i-1][x][y][z]+a[i].fi-1); //insert ()<-v2 if(z) cmn(f[i][x][min(y+2,2)][z-1],f[i-1][x][y][z]+2*a[i].fi+1); } } } } } int ans=1e9+10; for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) cmn(ans,f[n][i][j][1]); cout<<ans<<endl; } int main(){ int t=1; slv(); return 0; }