Шоколадка - революция
Аким получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпущена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Аким выбирают шоколадку Акиму в подарок. При этом цель первого - сэкономить, а второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Аким за ход либо берёт текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Акиму текущую шоколадку (если потомков нет). Первым ходит Аким.
Определите, на шоколадку какой стоимости может претендовать Аким.
Входные данные
Виды шоколадок занумерованы в некотором произвольном порядке, "Юлька" имеет номер 1. В первой строке входного файла находится одно целое число N - количество видов шоколадок (0 < N ≤ 200000). Далее следуют N строк, в каждой из которых задано 2 числа P_i и C_i - номер сорта-прародителя i-го и стоимость i-го сорта (0 ≤ P_i ≤ N,0 < C_i ≤ 1000000000; для "Юльки", у которой нет прародителя, указано P_1 = 0).
Выходные данные
Выведите в выходной файл одно число - стоимость шоколадки, которую получит Аким при правильных действиях как чиновника, так и своих.