eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сніговики

Сніговики

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

У містечку Меітечково учитель Андрій Сергійович Учитель купив через інтернет-магазин "Інтернет-магазин апаратів клонування" апарат для клонування сніговиків. Тепер діти можуть грати і навіть грають у подвір'є у наступну гру. Час від часу один з них обирає сніговика, який йому сподобався, клонує його і:

  • або додає йому зверху одну кулю;

  • або видаляє з ньоо верхню кулю (якщо сіеговик не порожній).

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

Вхідні дані

Перший рядок містить кількість дій n (1n200000). У рядку номер i + 1 міститься опис дії:

  • t m - клонувати сніговика номер t (0t < i) і додати зверху кулю масою m (0 < m1000);

  • t 0 - клонувати сніговика номер t (0t < i) і видалити верхню кулю. Гарантується, що сніговик не порожній.

У результаті дії i, описаної у рядку i + 1 створюється сніговик номер i. Спочатку є порожній сніговик з номером ноль.

Всі вхідні числа цілі.

Вихідні дані

Виведіть сумарну масу побудованих сніговиків.

Приклад

Вхідні дані #1
8
0 1
1 5
2 4
3 2
4 3
5 0
6 6
1 0
Вихідні дані #1
74
Автор Сергій Копеліович
Джерело Зимова Школа, Харків 2011, День 5