#include<bits/stdc++.h> #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize(2) #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10,mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n; vector<int>a,b; inline void chkmin(int &x,int y){if(x>y)x=y;} //bool DP[3][3][3][4][4][3][3][3]; struct _ { int x,y,z; _(int _x,int _y,int _z){x=_x,y=_y,z=_z;} }; vector<_>ve[3][3][3][4][4]; void init_allow(int x,int y,int z,int A,int B){ int f[4][3][3][3]; memset(f,0,sizeof(f)); f[0][x][y][z]=1; up(i,0,2){ int w=(i+1)%3; up(j,0,2){ up(k,0,2){ up(l,0,2)if(f[i][j][k][l]){ up(o1,0,(j==i))up(o2,0,(k==i))up(o3,0,(l==i)){ int total=o1+o2+o3; if(!i)total+=A+B; if(i==1)total+=B; if(total>3||(!total))continue; f[i+1][o1?w:j][o2?w:k][o3?w:l]|=f[i][j][k][l]; } } } } } up(i,0,2)up(j,i,2)up(k,j,2)if(f[3][i][j][k]||f[3][i][k][j]||f[3][j][i][k]||f[3][j][k][i]||f[3][k][i][j]||f[3][k][j][i])ve[x][y][z][A][B].p_b(_(i,j,k)); //up(i,0,2)up(j,0,2)up(k,0,2)chkmin(dp[i][j][k][i_2][j_2],f[3][i][j][k]); } int dp[4][5005][3][3][3]; void slv(){ n=read(); map<int,int>M1,M2; ll extra=0; up(i,1,n){ int w=read(),t=read(); if(w==1)M1[t]++; else M2[t]++; } for(auto it:M1){ int tot=it.p2; while(tot>=6){ extra+=2*it.p1+7; tot-=6; } up(i,1,tot)a.p_b(it.p1); } for(auto it:M2){ int tot=it.p2; while(tot>=6){ extra+=4*it.p1+5; tot-=6; } up(i,1,tot)b.p_b(it.p1); } up(i,0,2)up(j,0,2)up(k,0,2)up(x,0,3)up(y,0,3)if(x+y<=3)init_allow(i,j,k,x,y); //vector<vector<int> >dp[3][3][3]; /*up(i,0,2)up(j,0,2)up(k,0,2){ dp[i][j][k].resize((int)a.size()+1); up(p,0,min(2,(int)a.size()))dp[i][j][k][p].resize((int)b.size()+1,1e9); }*/ memset(dp,0x3f,sizeof(dp)); dp[0][0][0][0][0]=0; auto ZY=[&](int i,int j,int i_2,int j_2,int a,int b,int x,int y,int z,int init_val){ //if(init_val>=1e9)return; int A=i_2-i,B=j_2-j; init_val+=max(a,b)+b+1; for(auto it:ve[x][y][z][A][B]){ int i=it.x,j=it.y,k=it.z; chkmin(dp[i_2&3][j_2][i][j][k],init_val); } }; up(i,0,(int)a.size()){ int op=i&3; up(j,0,(int)b.size())up(x,0,2)up(y,x,2)up(z,y,2){ if(dp[op][j][x][y][z]>=1e9)continue; up(ii,0,min((int)a.size()-i,3))up(jj,0,min((int)b.size()-j,3-ii))ZY(i,j,i+ii,j+jj,(ii?a[i+ii-1]:1),(jj?b[j+jj-1]:1),x,y,z,dp[op][j][x][y][z]); } if(i<a.size()){ up(j,0,(int)b.size())up(x,0,2)up(y,x,2)up(z,y,2)dp[op][j][x][y][z]=1e9; } } cout<<dp[a.size()&3][b.size()][0][0][0]+extra; } int main(){ //freopen("ship.in","r",stdin),freopen("ship.out","w",stdout); slv(); return 0; }