eolymp
Задачи

Снеговики

Снеговики

Задача посвящается Станкевичу Андрею Сергеевичу - тренеру команды ITMO на Чемпионате Мира ACM

https://www.youtube.com/watch?v=3ndN6O11xfc

Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование - это процесс создания идентичной копии (клона).

В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин "Интернет-магазин аппаратов клонирования" аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:

  • либо добавляет ему сверху один шар;
  • либо удаляет из него верхний шар (если снеговик не пустой).

Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.

Входные данные

Первая строка содержит количество действий n (1n200000). В строке номер i + 1 содержится описание действия:

  • t m - клонировать снеговика номер t (0t < i) и добавить сверху шар массой m (0 < m1000);
  • t 0 - клонировать снеговика номер t (0t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.

В результате действия i, описанного в строке i + 1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.

Все входные числа целые.

Выходные данные

Выведите суммарную массу построенных снеговиков.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
Выходные данные #1
74
Автор Сергей Копелиович
Источник Зимняя школа, Харьков 2011, День 5