Острова 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$-я из следующих $N$ строк ($1 \le i \le 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

Примечание

Не нужно изменять направление приёмника ни на одном острове.