Problem A
ACKME Company Picnic

At ACKME Corporation, the annual company picnic has one very important rule: nobody should have to spend their day off with their boss. As the data science intern, your job is to help draw up the invitation list for the best possible company picnic. Luckily, ACKME has through careful evaluation assigned each employee a “fun rating”, and your task is simply to figure out the maximum total fun (summing over all invitees) for a company picnic.

The $n$ employees at ACKME are numbered $0, 1, \ldots , (n-1),$ and every employee except $\textrm{Employee}~ 0$ (the CEO) has exactly one boss. You can invite anyone, or their boss, to the picnic, but not both.

In the following diagrams, there is a visualization of the second and third sample inputs. The top number in each node is the employee number, and the bottom number is that employee’s fun rating. In each case, the rounded nodes denote the employees invited to the picnic. (These are possible optimal invitee lists; in general, there may be more than one optimal invitee list for any test case.)

Input

The first line of input contains a positive integer, $n \leq 200\, 000,$ specifying the number of employees. This is followed by $n$ lines, each of which gives the information for one of the employees, in order of increasing employee number (so the first of these $n$ lines is for $\textrm{Employee}~ 0).$ Each such line contains two space-separated numbers, the first of which is the employee’s fun rating, a non-negative integer no larger than $1\, 000\, 000,$ and the second of which is the employee number of the employee’s boss, an integer in the range $0 \ldots (n-1).$ Note that the “boss” listed for $\textrm{Employee}~ 0$ (who doesn’t actually have a boss) is $\textrm{always}~ 0,$ but this does not affect whether $\textrm{Employee}~ 0$ can be invited to the picnic.

It is guaranteed that the given employee-boss relationships yield a single hierarchy containing all $n$ employees, with $\textrm{Employee}~ 0$ at the top (ignoring the self-loop at $\textrm{Employee}~ 0).$

Output

Output a single non-negative integer, the maximum possible sum of invitee fun ratings.

8
16 0
166 7
15 7
359 2
77 7
187 3
211 7
83 0

829

10
1116 0
4848 7
359 0
4118 9
516 0
4298 1
2941 4
996 0
808 9
1120 2

13831

15
3815 0
1309 13
2778 0
6772 4
1469 1
3574 1
4899 0
4668 12
2585 6
17219 6
761 4
1050 14
2391 13
12889 0
34941 8

83602