You are going to visit a park, which is composed of N islands. The local management department has built a bridge from each island to another island. You can walk in both directions without crossing the bridge.

At the same time, there is a dedicated ferry between each pair of islands.

You prefer walking to taking a boat.

You want the total length of the bridge to be as long as possible, but subject to the following restrictions:

You can choose an island to visit.
No island can be visited more than once.
At any time, you can go from your current island S to another island d you have never been to. From S to D, there are the following methods:
(1) Walking: only possible if there is a bridge between the two islands. In this case, the length of the bridge will add up to the total distance you walk.
(2) Ferry: you can choose this method only if there is no combination of bridge and previously used ferry that can go from S to D (when checking whether it is reachable, you should consider all paths, including passing through the islands you have visited).
Note that you don't have to visit all the islands, and you may not be able to walk all the bridges.

Please write a program, give N bridges and their lengths, and calculate the maximum length of the bridge you can walk through according to the above rules.

Input format
Line 1 contains the integer N.

Line 2... N+1, each line contains two integers a and L. line i+1 indicates that a bridge leading to island a is built on island i, and the length of the bridge is L.

Output format
Output an integer representing the result.

For some tests, the answer may not fit into a 32 − bit integer.

Data range
2≤N≤106,
1≤L≤108

Input sample:
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
 Output example:
24

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int M = 2 * N;
ll st[N],ins[N];
//pox_cir retains the end position of each ring
ll pox_cir[N],cir[N],pre[N],tw[N];
ll prew[N],a[2 * N],s[2 * N],cnt_cir = 0;
ll d[N],da[N];
struct {
    ll v,next,w;
}edge[M];
ll head[N],cnt;
ll ans = 0;
ll q[2 * N],hh = 0,tt = 0;
void add(int u,int v,int w){
    edge[cnt].w = w;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
ll max(ll &a ,ll &b){
    return  a > b ? a : b;
}
void dfs_c(int u,int from){
    st[u] = ins[u] = true;
    for(int i = head[u];~i;i = edge[i].next){
        if((i ^ 1) == from)continue;
        ll v = edge[i].v,w = edge[i].w;
        pre[v] = u,prew[v] = w;
        if(!st[v])dfs_c(v,i);
        else if(ins[v]){
            cnt_cir ++;
            pox_cir[cnt_cir] = pox_cir[cnt_cir - 1];
            for(int k = u;k != v;k = pre[k]){
                tw[k] = prew[k];
                cir[++ pox_cir[cnt_cir]] = k;
            }
            tw[v] = prew[v],cir[++ pox_cir[cnt_cir]] = v;
        }
    }
    ins[u] = false;
}
ll dfs_d(int u,int fa){
    ll d1 = 0,d2 = 0;
    for(int i = head[u];~i; i = edge[i].next){
        ll v = edge[i].v,w = edge[i].w;
        if(v == fa || st[v])continue;
        ll d = dfs_d(v,u) + w;
        if(d >= d1)d2 = d1,d1 = d;
        else if(d > d2)d2 = d;
    }
    ans = max(ans,d1 + d2);
    return d1;
}
int main(){
    int n;
    memset(head,-1,sizeof head);
    cin>>n;
    int x,w;
    for(int i = 1;i <= n;i ++){
        scanf("%d %d",&x,&w);
        add(i,x,w),add(x,i,w);
    }
    for(int i = 1;i <= n;i ++){
        if(!st[i]){
            dfs_c(i,-1);
        }
    }
    // cout<<cnt_cir<<endl;
    // for(int i = 1;i <= pox_cir[cnt_cir];i ++){
    //     cout<<cir[i]<<" ";
    // }
    memset(st,0,sizeof st);
    for(int i = 1;i <= pox_cir[cnt_cir];i ++)st[cir[i]] = true;
    ll res = 0;
    for(int i = 1;i <= cnt_cir;i ++){
        ll ss = pox_cir[i - 1] + 1,ee = pox_cir[i];
        ll aans = 0;
        for(ll j = ss;j <= ee;j ++){
            ll v = cir[j];
            ans = 0;
            ll res = dfs_d(v,-1);
            d[v] = res,da[v] = ans;
            aans = max(aans,da[v]);
        }
        
        int m = ee - ss + 1;
    
        
        for(ll i = 0;i < m;i ++){
            a[i] = cir[ee - i];
            if(i != 0)s[i] = s[i - 1] + tw[a[i]];
            else s[i] = tw[a[i]];
        }
        for(int i = 0;i < m - 1;i ++)a[i + m] = a[i],s[i + m] = s[i + m - 1] + tw[a[i + m]];
        // for(int i = 0;i < 2 * m - 1;i ++){
        //     cout<<a[i]<<" "<<s[i]<<endl;
        // }
        hh = tt = 0;
        ll t = 0;
        for(int i = 0;i < 2 * m - 2;i ++){
            if(hh != tt && q[hh] <= i - (m - 1))hh ++;
            while(hh != tt && d[a[q[tt - 1]]] - s[q[tt - 1]] <= d[a[i]] - s[i])tt --;
            q[tt ++] = i;
            if(i >= m - 2){
                aans = max(aans,d[a[i + 1]] + s[i + 1] + d[a[q[hh]]] - s[q[hh]]);
            
            }
        }
        res += aans;
    }
    
    printf("%lld\n",res);
    
    return 0;
}