Looking for stones to collect and deliver to the guru in exchange for a chance to ask a question, Mumble stumbles upon a tree. (Don't ask why there is a tree in 80-below-zero Antarctica. There just is.) The tree happens to have stones on it. (Again, don't ask.) But some stones are hanging on the leaves, and other hanging on the tree branch junctions. In fact, some of these junctions or leaves have more than one stone hanging on them. (Stop asking!)
Intrigued, Mumble starts to count the stones. The number of stones inexplicably happens to be the same as the number of junctions and leaves! Oh my. What a discovery. (What did I say?)
By now, Mumble has totally forgotten about his all-important task of finding stones. Having such a beautiful correspondence between the number of stones and the number of junctions and leaves feels like such a waste when the stones are all over the place. (Umm...) Determined to right this wrong, Mumble sets himself on the task of rearranging the stones such that each junction and each leaf has exactly one stone stuck to it.
Mumble can move a stone by sliding it across a tree branch. (By, uh, sliding the string?) What is the minimum number of such moves Mumble must make before each junction has exactly one stone stuck on it?
Input
The first line contains n, the number of junctions and leaves.
The following n lines contain two integers each, pi and si, representing the parent of the ith junction and the number of stones hanging on that junction.
If the junction has no parent,
pi will be -1.
Output
Output a single integer indicating the minimum number of such moves Mumble must make before the tree has one stone per junction or leaf.
Limits
For 60% of test cases, 1 ≤ n ≤ 2,000.
For 100% of test cases, 1 ≤ n ≤ 1,000,000.
Sample Input 1
5
-1 0
0 0
0 2
1 0
1 3
Sample Output 1
4
Sample Input 2
7
1 3
2 0
3 0
-1 1
3 0
4 0
5 3
Sample Output 2
6