Cada una de las ~N~ amigas bovinas de Bessie (etiquetadas del ~1~ al ~N~) tiene su propia granja. Para cada ~1 \leq i \leq N~, la amiga ~i~ quiere visitar a la amiga ~a_i~ ~(a_i \neq i)~.

Dada una permutación ~(p_1, p_2, ..., p_N)~ del ~1~ al ~N~, las visitas se producen de la siguiente manera:

Para cada ~i~ del ~1~ al ~N~:

• Si la amiga ~a_{pi}~ ya ha salido de su granja, la amiga ~p_i~ permanece en la suya.
• De lo contrario, la amiga ~p_i~ sale de su granja para visitar la de la amiga ~a_{pi}. Esta visita produce un alegre mugido ~v_{pi}~ veces.

Calcula el número máximo posible de mugidos después de todas las visitas, considerando todas las permutaciones posibles ~p~.

Entrada

• La primera línea contiene ~N~.
• Para cada ~1 \leq i \leq N~, la línea i+1 contiene dos enteros separados por espacios: ~a_i~ y ~v_i~.

Salida

Un único entero que indica la respuesta.

Tenga en cuenta que el gran tamaño de los enteros involucrados en este problema puede requerir el uso de tipos de datos enteros de 64 bits (por ejemplo, un "long long" en C/C++).

Restricciones

• ~2 \leq N \leq 10^5~
• ~0 \leq v_{pi} \leq 10^9~

Ejemplo de Entrada

4
2 10
3 20
4 30
1 40

Ejemplo de Salida

90

Si ~p = (1, 4, 3, 2)~ entonces:

• El amigo 1 visita la granja del amigo 2, lo que resulta en 10 mugidos.
• El amigo 4 ve que el amigo 1 ya se ha ido, por lo que no sucede nada.
• El amigo 3 visita la granja del amigo 4, añadiendo 30 mugidos.
• El amigo 2 ve que el amigo 3 ya se ha ido, así que no pasa nada.

Esto da un total de ~10 + 30 = 40~ mugidos.

Por otro lado, si ~p = (2, 3, 4, 1)~, entonces:

• El amigo 2 visita la granja del amigo 3, causando 20 mugidos.
• El amigo 3 visita la granja del amigo 4, causando 30 mugidos.
• El amigo 4 visita la granja del amigo 1, causando 40 mugidos.
• El amigo 1 ve que el amigo 2 ya se ha ido, así que no pasa nada.

Esto da un total de ~20 + 30 + 40 = 90~ mugidos. Se puede demostrar que esta es la cantidad máxima posible después de todas las visitas, considerando todas las permutaciones ~p~.

Puntuación

• Los casos de prueba 2 y 3 satisfacen ~a_i \leq a_j~ para todo ~i \neq j~.
• Los casos de prueba 4 a 7 satisfacen ~N \leq 10^3~.
• Los casos de prueba 8 a 11 no satisfacen restricciones adicionales.

USACO 2022 US Open Contest, Silver. Problem 1. Visits.