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

Шоколадка - революция

Шоколадка - революция

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Аким получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпущена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Аким выбирают шоколадку Акиму в подарок. При этом цель первого - сэкономить, а второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Аким за ход либо берёт текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Акиму текущую шоколадку (если потомков нет). Первым ходит Аким.

Определите, на шоколадку какой стоимости может претендовать Аким.

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

Виды шоколадок занумерованы в некотором произвольном порядке, "Юлька" имеет номер 1. В первой строке входного файла находится одно целое число N - количество видов шоколадок (0 < N200000). Далее следуют N строк, в каждой из которых задано 2 числа P_i и C_i - номер сорта-прародителя i-го и стоимость i-го сорта (0P_iN,0 < C_i1000000000; для "Юльки", у которой нет прародителя, указано P_1 = 0).

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

Выведите в выходной файл одно число - стоимость шоколадки, которую получит Аким при правильных действиях как чиновника, так и своих.

Пример

Входные данные #1
8
0 4
5 3
1 2
5 1
1 5
4 8
3 6
3 7
Выходные данные #1
6