У Бесі є \(N\) (\(2\le N\le 10^5\)) приятелів - биків, послідовно пронумерованих \(1\ldots N\). Для кожного \(1\le i\le N\), бик \(i\) хоче відвідати бика \(a_i\) (\(a_i\neq i\)).

Задана перестановка \((p_1,p_2,\ldots, p_N)\) з \(1\ldots N\), що вказує як відбулися відвідини.

Для кожного \(i\) від \(1\) до \(N\):

• Якщо бик \(a_{p_i}\) вже пішов зі своєї ферми, то бик \(p_i\) залишається на своїй фермі.
• Інакше бик \(p_i\) йде зі своєї ферми на ферму \(a_{p_i}\). Цей візит завершується радісним "moo" вимовленим \(v_{p_i}\) раз (\(0\le v_{p_i}\le 10^9\)).

Обчисліть максимально можливу кількість "moo" після всіх візитів по всіх можливих перестановок \(p\).

Формат вхідних даних

Перший рядок містить число \(N\).

Для кожного \(1\le i\le N\), \(i+1\)-ий рядок містить два розділені пропуском цілих числа \(a_i\) і \(v_i\).

Формат вихідних даних

Одне ціле число – відповідь.

Зауважимо, що при обчисленнях може знадобитися використання 64-бітного типу цілих чисел (наприклад, long long C++).

Приклад вхідних даних

4
2 10
3 20
4 30
1 40

Приклад вихідних даних

90

Якщо \(p=(1,4,3,2)\) тоді

• Бик \(1\) відвідує бика \(2\) результат - \(10\) "moo".
• Бик \(4\) бачить, що бик \(1\) уже пішов, тому нічого не відбувається.
• Бик \(3\) відвідує бика \(4\), додається \(30\) "moo".
• Бик \(2\) бачить, що бик \(3\) уже пішов, тому нічого не відбувається.

Виходить всього \(10+30=40\) "moo".

З іншого боку, якщо \(p=(2,3,4,1)\) тоді

• Бик \(2\) відвідує бика \(3\), \(20\) "moo".
• Бик \(3\) відвідує бика \(4\), \(30\) "moo".
• Бик \(4\) відвідує бика \(1\), \(40\) "moo".
• Бик \(1\) бачить, що бик \(2\) уже пішов, тому нічого не відбувається.

Виходить \(20+30+40=90\) "moo". Можна довести, що це максимальна відповідь серед усіх перестановок \(p\).

ОЦІНЮВАННЯ:

• У тестах 2-3 \(a_i\neq a_j\) для всіх \(i\neq j\).
• У тестах 4-7 \(N\le 10^3\).
• У тестах 8-11 немає додаткових обмежень.