Problem statement

There is a village called Biwako, which consists of $ N $ islets floating on the lake. Biwako Village has a simple bridge with $ N-1 $ books. The islands are numbered from $ 0 $ to $ N-1 $, and the bridges are numbered from $ 0 $ to $ N-2 $. The $ i $ bridge directly connects the $ i + 1 $ island and the $ p_i $ island, and is $ w_i $ in length. Villagers can move between islands through several bridges.

At the suggestion of a villager, a relay tournament will be held in Biwako Village. However, since there is no closed road in Biwako Village and trucks cannot be prepared, I decided to make a closed road by replacing the existing bridge by only $ 1 $. Find the length of the cycle that can be prepared by this operation and that has the maximum length.

Constraint

$ 2 \ leq N \ leq 100000 $
$ 0 \ leq p_i \ leq N-1 $
$ 1 \ leq w_i \ leq 1000 $
All integers
Reachable between all islands

sample

The illustration of each sample is as follows.

<image>

Sample input 1


Five
0 1
0 2
0 3
0 4


Sample output 1


9


Sample input 2


12
0 6
1 1
0 3
3 4
0 2
5 1
6 1
0 2
8 1
9 1
10 2


Sample output 2


19


Sample input 3


2
0 1


Sample output 3


1




input

$ N $
$ p_0 \ w_0 $
$ \ vdots $
$ p_ {n-2} \ w_ {n-2} $

output

Print the answer on the $ 1 $ line.

Example

Input

5
0 1
0 2
0 3
0 4


Output

9
#include <bits/stdc++.h>

using namespace std;

#define MAX_N 100000

struct edge {
  int to, cost;
  edge(){}
  edge(int to, int cost):to(to), cost(cost){}
};

using Pi = pair<int, int>;

int N;
vector<edge> graph[MAX_N];

Pi dfs(int u, int p) {
  Pi res = Pi(0, u);
  for(edge& e : graph[u]) {
    if(e.to == p) continue;
    Pi tmp = dfs(e.to, u);
    tmp.first += e.cost;
    res = max(res, tmp);
  }
  return res;
}
Pi diameter() {
  Pi p = dfs(0, -1);
  Pi q = dfs(p.second, -1);
  return Pi(p.second, q.second);
}

int bi[MAX_N], ei[MAX_N];
int idx;
void euler(int u, int p) {
  bi[u] = idx++;
  for(edge& e : graph[u]) {
    if(e.to == p) continue;
    euler(e.to, u);
  }
  ei[u] = idx;
}

struct SegmentTree {
  vector<int> data;
  int sz;
  SegmentTree(int n) {
    sz = 1; while(sz < n) sz *= 2;
    data.resize(2*sz-1, 0);
  }
  void set(int k, int x) {
    k += sz-1;
    data[k] = x;
    while(k > 0) {
      k = (k-1)/2;
      data[k] = max(data[2*k+1], data[2*k+2]);
    }
  }
  int query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return data[k];
    int vl = query(a, b, 2*k+1, l, (l+r)/2);
    int vr = query(a, b, 2*k+2, (l+r)/2, r);
    return max(vl, vr);
  }
  int query(int a, int b) {
    return query(a, b, 0, 0, sz);
  }
};

int cost[MAX_N];
void dfs2(int u, int p, int d) {
  cost[u] = d;
  for(edge& e : graph[u]) {
    if(e.to == p) continue;
    dfs2(e.to, u, d+e.cost);
  }
}

int solve(int root) {
  idx = 0;
  dfs2(root, -1, 0);
  euler(root, -1);
  SegmentTree seg(N);
  for(int i = 0; i < N; i++) {
    seg.set(bi[i], cost[i]);
  }
  int res = 0;
  for(int i = 0; i < N; i++) {
    for(edge& e : graph[i]) {
      int u = (cost[i] < cost[e.to] ? e.to : i);
      //cout << bi[u] << " " << ei[u] << endl;
      int c = max(seg.query(0, bi[u]), seg.query(ei[u], N));
      res = max(res, c+e.cost);
      //cout << root << " "<<i << " " << u << " " << c << " " << c+e.cost << endl;
    }
  }
  return res;
}

int main() {
  cin >> N;
  for(int i = 0; i < N-1; i++) {
    int p, w;
    cin >> p >> w;
    graph[p].emplace_back(i+1, w);
    graph[i+1].emplace_back(p, w);
  }
  Pi p = diameter();
  int ans1 = solve(p.first);
  int ans2 = solve(p.second);
  //cout << p.first << " "<<p.second << endl;
  //cout << ans1 << " " << ans2 << endl;
  cout << max(ans1, ans2) << endl;
  return 0;
}