#pragma GCC optimize("O5,unroll-loops,inline,fast-math") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include<bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) #define int long long using namespace std; const int N = 1e6+5; int n,to[N],in[N],w[N],dp1[N],dp2[N],dia[N],dq1[2*N],dq2[2*N],q[2*N],qf=0,qb=0,u,v,ans=0,node[N],dist[N]; signed main(void){ exoworldgd; cin >> n; for (int i = 1; i <= n; i++) cin >> to[i] >> w[i], in[to[i]]++; for (int i = 1; i <= n; i++) if (!in[i]) q[qb++] = i; while(qf < qb){ u=q[qf++],v=to[u],dp2[v]=max(dp2[v],dp1[u]+w[u]); if(dp2[v] > dp1[v]) swap(dp1[v],dp2[v]); dia[v] = max({dia[v],dia[u],dp1[v]+dp2[v]}), !--in[v] ? q[qb++]=v : 0; } for(int i = 1; i <= n; i++){ if (!in[i]) continue; int nc=0,sum=0,curr=i,mx=0,df=0,db=0; do {node[nc]=curr, dist[nc]=sum, in[curr]=0, sum+=w[curr], curr = to[curr], nc++; }while(curr^i); for (int j = 0; j < nc; j++)mx = max(mx,dia[node[j]]); for (int j=0; j< nc; j++) { u=node[j],v=dp1[u]-dist[j]; while(db > df && dq1[db-1] <= v) db--; dq1[db]=v, dq2[db]=j, db++; } for (int j =0; j < nc; j++){ u=node[j],v=dp1[u]-dist[j]-sum; while (db > df && dq2[df] == j) df++; if (db > df) mx=max(mx,dp1[u]+dist[j]+sum+dq1[df]); while (db > df && dq1[db-1] <= v) db--; dq1[db]=v, dq2[db]=j, db++; } ans+=mx; } cout << ans; }