#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ll long long using namespace std; const int Nmax=1e5+5; vector<int> poz[Nmax]; pair<int,int> a[Nmax]; void unite(vector<int>& a,vector<int>& b) { if(a.size()<b.size()) swap(a,b); for(int x:b) a.push_back(x); b.clear(); b.shrink_to_fit(); return; } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n; cin>>n; int maxi=0; for(int i=1; i<=n; i++) { cin>>a[i].first>>a[i].second; } sort(a+1,a+n+1); for(int i=1; i<=n; i++) { int h=a[i].first,k=a[i].second; if(h!=a[i-1].first) { for(int j=a[i-1].first+1; j<=h; j++) poz[0].push_back(j); } int last=0; for(int cnt=0; cnt<=maxi; cnt++) { if(poz[cnt].size()<k) { k-=poz[cnt].size(); } else if(poz[cnt].size()==k) { last=cnt+1; k=0; break; } else { last=cnt; break; } } for(int cnt=1; cnt<=last-2; cnt++) { swap(poz[cnt],poz[0]); } if(poz[last].size()-k<k) { k=poz[last].size()-k; vector<int> ext; while(k>0) { ext.push_back(poz[last].back()); poz[last].pop_back(); k--; } unite(poz[last+1],poz[last]); if(last==0) { swap(ext,poz[last]); } else { unite(ext,poz[last-1]); swap(poz[last-1],poz[0]); swap(ext,poz[last]); } } else { vector<int> ext; while(k>0) { ext.push_back(poz[last].back()); poz[last].pop_back(); k--; } unite(poz[last+1],ext); if(last>0) { unite(poz[last],poz[last-1]); swap(poz[last-1],poz[0]); } } maxi=max(maxi,last+1); } ll ans=0; for(ll cnt=0; cnt<=maxi; cnt++) { ll nums=poz[cnt].size(); ans+=nums*cnt*(cnt-1)/2; } cout<<ans<<'\n'; return 0; }