Задачі
Шоколадка - революція
Шоколадка - революція
Аким отримав золоту медаль на \textbf{IOI}, за що від уряду йому належить подяка у вишляді шоколадки. На даний момент є \textbf{N} видів шоколадок, які виробляє державна шоколадна фабрика. У кожної шоколадки є вартість. Крім того, у кожного вида, крім шоколадки "Юлька", є вид-предок. Відомо, що предком може бути лише шоколадка, яка була випущена хронологічно раніше. Історично самий перший вид - "Юлька". Чиновник та Аким вибирають шоколадку Акиму у подарунок. При цьому мета першого - зекономити, а другого - отримати настільки дорогу шоколадку, наскільки це можливо. Починається вибір з "Юльки". Аким за хід або бере поточну шоколадку, або змінює свій вибір на шоколадку-потомка (якщо це можливо). Чиновнику ж здається, що пізніше випущені види гірші і дешевші, тому він змінює вибір на шоколадку-потомка (якщо це можливо), або купує Акиму поточну шоколадку (якщо потомків немає). Першим ходить Аким.
Визначте, на шоколадку якої вартості зоже претендувати Аким.
\InputFile
Види шоколадок занумеровано у деякому довільному порядку, "Юлька" має номер \textbf{1}. У першому рядку вхідного файлу знаходиться одне ціле число \textbf{N} - кількість видів шоколадок (\textbf{0} < \textbf{N} ≤ \textbf{200000}). Далі йде \textbf{N} рядків, у кожному з яких задано \textbf{2} числа \textbf{P_i} та \textbf{C_i} - номер сорту-пркедка \textbf{i}-го та вартість \textbf{i}-го сорту (\textbf{0} ≤ \textbf{P_i} ≤ \textbf{N},\textbf{0} < \textbf{C_i} ≤ \textbf{1000000000}; для "Юльки", у якої немає предка, вказано \textbf{P_1 = 0}).
\OutputFile
Виведіть у вихідний файл одне число - вартість шоколадки, яку отримає Аким при правильних діях як чиновника, так і своїх.
Вхідні дані #1
8 0 4 5 3 1 2 5 1 1 5 4 8 3 6 3 7
Вихідні дані #1
6