Архіпелаг JOI — невелика острівна держава в Тихому океані. Він складається з $N$ островів, пронумерованих від $1$ до $N$.

Зв'язок між островами архіпелагу JOI здійснюється переважно радіохвилями. На кожному острові є по одному передавачу та приймачу. Передавач може надсилати радіохвилі в усіх напрямках, але приймач може приймати їх лише з певного напрямку. Тому кожен приймач може приймати радіохвилі лише з одного конкретного острова. Проте, повернувши приймач, можна змінити острів, з якого він приймає радіохвилі.

Зараз приймач на острові $i$ ($1\le i\le N$) може приймати радіохвилі з острова $A_i$ ($A_i\ne i$). Вартість зміни напрямку приймача на острові $i$ дорівнює $C_i$ незалежно від того, як саме змінюється напрямок.

На архіпелазі JOI працює державна телеграфна служба. Якщо приймач острова $j$ ($1\le j\le N$, $j\ne i$) може приймати радіохвилі з острова $i$ ($1\le i\le N$), то з острова $i$ можна надіслати телеграму на острів $j$ радіозв'язком. Телеграми також можна передавати через кілька проміжних островів. Тобто для попарно різних островів $i,j,k$ ($1\le i,j,k\le N$), якщо можна надіслати телеграму з $i$ на $j$ та з $j$ на $k$, то можна надіслати її з $i$ на $k$. Надсилати телеграми будь-яким способом, окрім радіозв'язку, неможливо.

Ви — міністр зв'язку архіпелагу JOI — хочете забезпечити можливість надсилати телеграми з будь-якого острова на будь-який інший. Для цього, можливо, доведеться змінити напрямки приймачів на деяких островах. Вартість таких змін дорівнює сумі вартостей зміни напрямку кожного з цих приймачів.

Обчисліть найменшу вартість, потрібну для забезпечення можливості надсилати телеграми з будь-якого острова на будь-який інший.

Завдання

За кількістю островів архіпелагу JOI та інформацією про приймач на кожному острові напишіть програму, яка знаходить найменшу вартість забезпечення можливості надсилати телеграми з будь-якого острова на будь-який інший.

Вхідні дані

Прочитайте такі дані зі стандартного введення.

• Перший рядок містить ціле число $N$. Воно означає, що архіпелаг JOI складається з $N$ островів.
• $i$-тий рядок ($1\le i\le N$) із наступних $N$ рядків містить цілі числа $A_i,C_i$, розділені пробілом. Це означає, що приймач на острові $i$ зараз може приймати радіохвилі з острова $A_i$, а вартість зміни його напрямку дорівнює $C_i$.

Вихідні дані

Виведіть у стандартне виведення в одному рядку найменшу вартість, потрібну для забезпечення можливості надсилати телеграми з будь-якого острова на будь-який інший.

Обмеження

Усі вхідні дані задовольняють такі умови.

• $2\le N\le 100\,000$.
• $1\le A_i\le N$ ($1\le i\le N$).
• $A_i\ne i$ ($1\le i\le N$).
• $1\le C_i\le 1\,000\,000\,000$ ($1\le i\le N$).

Підзадачі

Підзадача 1 [10 балів]

• Виконується $N\le 10$.

Підзадача 2 [30 балів]

• Виконується $N\le 15$.

Підзадача 3 [30 балів]

• Виконується $N\le 3\,000$.

Підзадача 4 [30 балів]

Додаткових обмежень немає.

Приклади

Вхідні дані 1

4
2 2
1 4
1 3
3 1

Вихідні дані 1

4

Примітка

Змінимо напрямок приймача на острові $2$, щоб він приймав радіохвилі з острова $4$. Тоді можна буде надсилати телеграми з будь-якого острова на будь-який інший, а вартість становитиме $4$.

Жодна зміна напрямків приймачів не дає вартості меншої за $4$, тому виводимо $4$.

Вхідні дані 2

4
2 2
1 6
1 3
3 1

Вихідні дані 2

5

Примітка

Спочатку змінимо напрямок приймача на острові $1$, щоб він приймав радіохвилі з острова $4$. Потім змінимо напрямок приймача на острові $3$, щоб він приймав радіохвилі з острова $2$. Тоді можна буде надсилати телеграми з будь-якого острова на будь-який інший, а вартість становитиме $2+3=5$.

Жодна зміна напрямків приймачів не дає вартості меншої за $5$, тому виводимо $5$.

Вхідні дані 3

4
2 2
1 3
4 2
3 3

Вихідні дані 3

4

Примітка

Достатньо змінити напрямки приймачів на островах $1$ та $3$.

Вхідні дані 4

3
2 1
3 1
1 1

Вихідні дані 4

0

Примітка

Не потрібно змінювати напрямок жодного приймача.