El archipiélago JOI es un pequeño país insular situado en el océano Pacífico. Tiene $N$ islas, numeradas del $1$ al $N$.

En el archipiélago JOI, la comunicación entre islas se realiza principalmente por radio. Cada isla tiene un transmisor y un receptor de radio. El transmisor puede enviar ondas de radio en todas las direcciones, pero el receptor solo puede recibirlas desde una dirección concreta. Por tanto, cada receptor solo puede recibir las ondas de una única isla determinada. Sin embargo, al cambiar la orientación del receptor se puede cambiar la isla de la que recibe las ondas.

Actualmente, el receptor de la isla $i$ ($1 \le i \le N$) puede recibir las ondas de la isla $A_i$ ($A_i \ne i$). Además, el coste de cambiar la orientación del receptor de la isla $i$ es $C_i$, independientemente de cómo se cambie su orientación.

El archipiélago JOI ofrece un servicio público de telegramas. Cuando el receptor de la isla $j$ ($1 \le j \le N$, $j \ne i$) puede recibir las ondas de la isla $i$ ($1 \le i \le N$), se puede enviar un telegrama de la isla $i$ a la isla $j$ mediante comunicación por radio. Los telegramas también pueden enviarse pasando por varias islas. Es decir, para las islas $i,j,k$ ($1 \le i,j,k \le N$, con $i,j,k$ distintos entre sí), si se puede enviar un telegrama de la isla $i$ a la isla $j$ y de la isla $j$ a la isla $k$, entonces se puede enviar un telegrama de la isla $i$ a la isla $k$. No se pueden enviar telegramas por ningún medio distinto de la comunicación por radio.

Tú eres el ministro de Comunicaciones del archipiélago JOI y quieres que se puedan enviar telegramas desde cualquier isla a cualquier otra. Para ello, puede ser necesario cambiar la orientación de los receptores de algunas islas. El coste de cambiar la orientación de varios receptores es la suma de los costes de cambiar la orientación de cada uno de ellos.

Calcula el coste mínimo necesario para que se puedan enviar telegramas desde cualquier isla a cualquier otra.

Tarea

Dados el número de islas del archipiélago JOI y la información sobre el receptor de cada isla, escribe un programa que calcule el coste mínimo necesario para que se puedan enviar telegramas desde cualquier isla a cualquier otra.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene un entero $N$. Este indica que el archipiélago JOI tiene $N$ islas.
• La línea $i$ ($1 \le i \le N$) de las $N$ líneas siguientes contiene los enteros $A_i,C_i$ separados por un espacio. Estos indican que el receptor de la isla $i$ puede recibir actualmente las ondas de la isla $A_i$, y que el coste de cambiar su orientación es $C_i$.

Salida

Escribe en una línea de la salida estándar el coste mínimo necesario para que se puedan enviar telegramas desde cualquier isla a cualquier otra.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $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$).

Subtareas

Subtarea 1 [10 puntos]

• Se cumple $N \le 10$.

Subtarea 2 [30 puntos]

• Se cumple $N \le 15$.

Subtarea 3 [30 puntos]

• Se cumple $N \le 3\,000$.

Subtarea 4 [30 puntos]

Sin restricciones adicionales.

Ejemplos

Entrada 1

4
2 2
1 4
1 3
3 1

Salida 1

4

Nota

Cambia la orientación del receptor de la isla $2$ para que pueda recibir las ondas de la isla $4$. Así se podrán enviar telegramas desde cualquier isla a cualquier otra, y el coste será $4$.

Ninguna forma de cambiar la orientación de los receptores puede dar un coste inferior a $4$, por lo que se escribe $4$.

Entrada 2

4
2 2
1 6
1 3
3 1

Salida 2

5

Nota

Primero, cambia la orientación del receptor de la isla $1$ para que pueda recibir las ondas de la isla $4$. Después, cambia la orientación del receptor de la isla $3$ para que pueda recibir las ondas de la isla $2$. Así se podrán enviar telegramas desde cualquier isla a cualquier otra, y el coste será $2+3=5$.

Ninguna forma de cambiar la orientación de los receptores puede dar un coste inferior a $5$, por lo que se escribe $5$.

Entrada 3

4
2 2
1 3
4 2
3 3

Salida 3

4

Nota

Basta con cambiar la orientación de los receptores de las islas $1$ y $3$.

Entrada 4

3
2 1
3 1
1 1

Salida 4

0

Nota

No es necesario cambiar la orientación del receptor de ninguna isla.