Problem D
Dividing Kingdom

The Kingdom of Byteland has $n$ cities, numbered from $1$ to $n$. There are exactly $n-1$ roads in the kingdom, each connects a pair of cities. Using these roads, it is possible to go from any city to any other city.

The king of Byteland wants to divide the kingdom into two halves and pass down each half to one of his two sons. This would be done by removing exactly one road, splitting the kingdom into two connected components.

This turns out to be a non-trivial task! To avoid fighting between his sons, the king needs to divide the kingdom fairly. For each half, he defines its diameter as the longest simple path connecting two cities in that half. The king wants the difference between the diameters of the two halves to be minimum.

Note: A simple path from city $s$ to city $t$ is an ordered sequence of cities $v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_ k$, where $v_0 = s, v_ k = t$, and all $v_ i$ are unique. For each valid index $i$, $v_ i$ and $v_{i+1}$ are connected directly by some road. The length of a path is the sum of the length of all roads connecting $v_ i$ and $v_{i+1}$.

Please help the king!

Input

The input contains multiple test cases, each test case is presented as below:

• The first line contains a positive integer $n$ $(2 \le n \le 3 \cdot 10^5)$ — the number of cities. The sum of $n$ in all test cases does not exceed $10^6$.

• In the next $n-1$ lines, the $i$-th line $(i = 1 \ldots n-1)$ contains two integers $p_ i$ and $l_ i$ $(1 \le p_ i \le i, 1 \le l_ i \le 10^9)$, indicating that two cities $p_ i$ and $i+1$ are connected by a road of length $l_ i$.

The input ends with a line containing a single $0$ which is not a test case.

Output

For each test case, print a single line containing a single integer — the minimum difference between the two diameters.

Explanation of the first sample

The figure below demonstrates the first test case. One way to obtain an optimal solution is to remove the road between city $2$ and city $7$ (marked by dashed line). By removing this road, the kingdom is split into two halves, whose cities are marked in orange and blue colors. The longest simple paths are marked in bolder colors.

12
1 3
1 3
3 2
1 3
1 5
2 1
7 2
8 2
9 3
8 2
11 3
4
1 10
2 10
3 10
4
1 20
2 10
3 10
0

0
0
10