Снеговики
Задача посвящается Станкевичу Андрею Сергеевичу - тренеру команды ITMO на Чемпионате Мира ACM
https://www.youtube.com/watch?v=3ndN6O11xfc
Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование - это процесс создания идентичной копии (клона).
В местечке Местячково учитель Андрей Сергеевич Учитель купил через интернет-магазин "Интернет-магазин аппаратов клонирования" аппарат для клонирования снеговиков. Теперь дети могут играть и даже играют во дворе в следующую игру. Время от времени один из них выбирает понравившегося снеговика, клонирует его и:
либо добавляет ему сверху один шар;
либо удаляет из него верхний шар (если снеговик не пустой).
Учитель Андрей Сергеевич Учитель записал последовательность действий и теперь хочет узнать суммарную массу всех построенных снеговиков.
Giriş verilənləri
Первая строка содержит количество действий n (1 ≤ n ≤ 200000). В строке номер i + 1 содержится описание действия:
t m - клонировать снеговика номер t (0 ≤ t < i) и добавить сверху шар массой m (0 < m ≤ 1000);
t 0 - клонировать снеговика номер t (0 ≤ t < i) и удалить верхний шар. Гарантируется, что снеговик не пустой.
В результате действия i, описанного в строке i + 1 создается снеговик номер i. Изначально имеется пустой снеговик с номером ноль.
Все входные числа целые.
Çıxış verilənləri
Выведите суммарную массу построенных снеговиков.