Petya received a gold medal at IOI, for which he received a thank you from the government in the form of a chocolate bar. At the moment, there are N types of chocolates, which are produced by the state chocolate factory. Each chocolate bar has a value. In addition, each species, except for the Yulka chocolate bar, has a progenitor species. It is known that only a chocolate bar that was released chronologically earlier can be the progenitor. Historically, the very first species is "Yulka". The official and Petya choose a chocolate bar for him as a gift. At the same time, the goal of the first is to save money, the second is to get as expensive a chocolate bar as possible. The choice begins with "Yulka". Petya either takes the current chocolate bar or changes his choice to a descendant chocolate bar (if possible). It seems to the official that the types released later are worse and cheaper, so he changes his choice to a descendant chocolate bar (if possible), or buys Petya a chocolate bar (if there are no descendants). They walk in turn, Petya is the first. Determine what price Petya can claim for a chocolate bar.
Input
First enter the number 0 < N <= 200000 - number of species. "Yulka" has number 1. Next come N lines with pairs of numbers 0 <= Pi <= N - the number of the ancestor variety > 0) and 0 < Ci <= 1000000000 - the cost of the i-th grade.
Output
Print the cost of a chocolate that Petya can guarantee himself if he does the right thing.
|
Enter |
Output |
|
8
04
5 3
1 2
5 1
15
48
36
37
|
6 |