Data structures contest - high level


This problem is devoted to Stankevich Andrey Sergeevich - the coach of ITMO ACM team


Winter. The 2012 year. Against the backdrop of coming apocalypse and the end of the world, the news passed unnoticed about the latest breakthroughs in the areas of cloning and snowmen: the snowmen cloning. You certainly know, but we remind you, that the snowman consists of zero or more balls, vertically stacked on each other, and cloning is the process of creating an identical copy (clone).

In the place Mestyachkovo the teacher Andrey Sergeevich Uchitel purchased through the online store "Shop apparatus cloning" the device for snowmen cloning. Now even kids can play and they do play in the yard the next game. From time to time one of the kids chooses the snowman he likes, clones it and:

  • either adds the ball to the top;

  • or removes the top ball (if the snowman is not empty).

The teacher Andrey Sergeevich Uchitel wrote the sequence of actions and now wants to know the total mass of all built snowmen.


The first line contains the number of actions n (1n200000). The line i + 1 describes the action:

  • t m - clone the snowman number t (0t < i) and add the ball to the top of weight m (0 < m1000);
  • t 0 - clone the snowman number t (0t < i) and remove the top ball. It is guaranteed that the snowman is not empty.

The result of action i, which is described in line i + 1, is a new snowman number i. Initially there is an empty snowman with number zero.

All input numbers are integer.


Print the total mass of all built snowmen.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
Output example #1
Author Sergey Kopeliovich
Source Winter School, Kharkov, 2011, Day 5