e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Сніговики

Сніговики

Зима. 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