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

 

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

Сначала вводится число 0 < N <= 200000 - количество видов. "Юлька" имеет номер 1. Далее идут N строк с парами чисел 0 <= P_i <= N - номер сорта-предка (для шоколадки "Юлька" указан 0, у остальных P_i > 0) и 0 < Ci <= 1000000000 - стоимость i-го сорта.

 

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

Выведите стоимость шоколадки, которую Петя может себе гарантировать при правильных действиях.

Ввод	Вывод
8 0 4 5 3 1 2 5 1 1 5 4 8 3 6 3 7	6

Загруженные файлы:

---

Примечание учителя: