Usoperanto
Usoperanto — це штучна мова, розроблена та регульована Академією Usoperanto. Академія зараз розглядає можливість створення Строгого Usoperanto, варіації мови, призначеної для офіційних документів.
У Usoperanto кожне слово може модифікувати не більше одного іншого слова, і модифікатори завжди розташовуються перед модифікованими словами. Наприклад, з іменником uso ("істина"), модифікованим прикметником makka ("повна"), кажуть makka uso, а не uso makka. Однак, не існує правил щодо порядку кількох слів, що модифікують одне і те ж слово, тому, якщо uso модифікується ще одним прикметником beta ("очевидна"), можна сказати як makka beta uso, так і beta makka uso.
У Строгому Usoperanto порядок слів буде обмежений відповідно до вартості модифікації. Слова у фразі повинні бути розташовані так, щоб загальна вартість модифікації була мінімальною. Кожній парі модифікатор-модифіковане слово призначається вартість, рівна кількості літер між двома словами; загальна вартість модифікації — це сума вартостей усіх пар модифікатор-модифіковане слово у фразі. Наприклад, пара makka та uso у фразі makka beta uso має вартість 4 для beta (чотири літери). Оскільки пара beta та uso не має слів між ними, вартість дорівнює нулю, makka beta uso має загальну вартість модифікації 4. Аналогічно, beta makka uso має загальну вартість модифікації 5. Застосовуючи правило "мінімальної загальної вартості модифікації", makka beta uso є кращим за beta makka uso у Строгому Usoperanto.
Ваше завдання в цій задачі — написати програму, яка, отримавши набір слів у фразі, знаходить правильний порядок слів у Строгому Usoperanto та повідомляє загальну вартість модифікації.
Вхідні дані
Формат вхідних даних наступний.
N
M_0 L_0
…
M_{N−1} L_{N−1}
Перший рядок містить ціле число N (1 ≤ N ≤ 10^6). N — це кількість слів у фразі.
Кожен з наступних N рядків містить два цілі числа M_i (1 ≤ M_i ≤ 10) і L_i (−1 ≤ L_i ≤ N−1, L_i ≠ i), що описують i-те слово (0 ≤ i ≤ N−1). M_i — це кількість літер у слові. L_i вказує на модифікацію: L_{i}= −1 означає, що воно не модифікує жодного слова; інакше воно модифікує L_i-те слово.
Зверніть увагу, що перший приклад вхідних даних нижче можна інтерпретувати як випадок uso-beta-makka.
Вихідні дані
Виведіть загальну вартість модифікації.