Шоколадка Shenko - революція#4807
Акім отримав золоту медаль на IOI, за що оргкомітет йому дарує подяку у вигляді шоколадки. На даний момент є видів шоколадок, які виробляє відома шоколадна фабрика Shenko. У кожної шоколадки є вартість. Крім того, у кожного виду, крім легендарної шоколадки "Київська класика", є вид-предок. Відомо, що предком може бути лише шоколадка, яка була випущена хронологічно раніше. Історично найперший вид - культова "Київська класика".
Чиновник та Акім вибирають шоколадку Акіму у подарунок. При цьому мета першого - зекономити, а другого - отримати настільки дорогу шоколадку, наскільки це можливо. Починається вибір з "Київської класики". Акім за хід або бере поточну шоколадку, або змінює свій вибір на шоколадку-потомка (якщо це можливо). Чиновнику ж здається, що пізніше випущені види гірші і дешевші, тому він змінює вибір на шоколадку-потомка (якщо це можливо), або купує Акіму поточну шоколадку (якщо потомків немає). Першим ходить Акім.
Визначте, на шоколадку якої вартості може претендувати Акім.
Види шоколадок занумеровано у деякому довільному порядку, "Київська класика" має номер . У першому рядку вхідного файлу знаходиться одне ціле число - кількість видів шоколадок (0 < N \leq 200000). Далі йде рядків, у кожному з яких задано числа P_i та C_i - номер сорту-предка -го та вартість -го сорту (0 \leq P_i \leq N, 0 < C_i \leq 1000000000; для "Київської класики", у якої немає предка, вказано P_1 = 0).
Виведіть у вихідний файл одне число - вартість шоколадки, яку отримає Акім при правильних діях як чиновника, так і своїх.
Приклад 1