Estas visitando un parque que tiene ~N~ islas. Desde cada isla ~i~, se ha construido exactamente un puente. La longitud de un puente ~i~, es denotada por ~Li~. El número total de puentes en el parque es ~N~. A pesar de que cada puente fue construido desde una isla hacia otra, ahora se puede atravesar en ambas direcciones. Además, para cada par de islas, hay una única lancha que viaja entre ellas.

Para ti resulta mejor caminar que andar en lancha, porque quieres maximizar la suma de las longitudes de los puentes que cruzas, sujeto a las siguientes condiciones:

• Debes iniciar la visita desde una isla que seleccionas.

• No puedes visitar una isla más de una vez.

• En el momento es que deseas moverte desde una isla ~S~ hacia otra isla ~D~ que no has visitado antes. Debes ir desde ~S~ hacia ~D~ por medio de:

o Caminado: Es posible solo si existe un puente entre ambas islas. En este caso la longitud de dicho puente se suma a la distancia total que has caminado.

o Lancha: Puedes elegir esta opción sí y solo sí ~D~ no es alcanzable desde ~S~ usando cualquier combinación de puentes y/o lanchas usadas previamente. (Cuando chequeas si es alcanzable o no, debes considerar todos los caminos, inclusive los caminos a través de las islas que tú ya has visitado)

Observa que no tienes que visitar todas las islas, y esto puede ser imposible al cruzar todos los puentes.

TAREA

Escribe un programa que, dados los ~N~ puentes junto con sus distancias, calcule la máxima distancia que puedes caminar cruzando los puentes acatando las condiciones que se describieron arriba.

RESTRICCIONES

~2 <= N <= 1 000 000~ Número de Islas en el parque.
~1<= Li <= 100 000 000~ Longitud del Puente ~i~.

ENTRADA

Tu programa debe leer desde la entrada estándar los siguientes datos:

• La línea 1 contiene un entero ~N~, el número de islas en el parque. Las islas son enumeradas desde 1 hasta ~N~, inclusive.

• Cada una de las siguientes ~N~ líneas describen un puente. La ~i-esima~ de estas líneas describen el puente construido desde la ~i-esima~ isla mediante dos enteros separados por un espacio. El primer entero representa la isla en el otro extremo de puente, el segundo entero representa la distancia ~Li~ de dicho puente. Puedes asumir que por cada puente, sus puntos extremos son siempre dos islas diferentes.

SALIDA

Tu programa debe escribir en la salida estándar una sola línea que contiene un entero, la distancia máxima posible caminada.

Observación 1: Para algunos de los casos de prueba la respuesta no cabe dentro de un entero de 32-bits, quizás necesites int64 en Pascal y long long en C/C++ para obtener todos los puntos en este problema.

Observación 2: Cuando ejecutas programas en Pascal dentro del ambiente de competencia, es significativamente lento leer tipos de datos de 64-bits en lugar de 32-bits desde la entrada estándar, incluso cuando el valor leído cabe dentro de 32-bits. Recomendamos que leas los datos de entrada dentro de un tipo de datos de 32-bits.

Ejemplo de Entrada

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

Ejemplo de Salida

24

Los ~N=7~ puentes en el ejemplo son: ~(1-3), (2-7), (3-4), (4-1), (5-1), (6-3)~ and ~(7-2)~. Observa que hay dos puentes diferentes conectando a las islas 2 y 7. Puedes lograr caminar la máxima distancia como sigue:

o Iniciar en la Isla 5.

o Camina el puente de longitud 9 para alcanzar la isla 1.

o Camina el puente de longitud 8 para alcanzar la isla 3.

o Camina el puente de longitud 4 para alcanzar la isla 6.

o Toma la lancha entre las islas 6 y 7 y toma la lancha desde la isla 6 hacia la isla 7.

o Camina el puente de longitud 3 para alcanzar la isla 2.

Al final estas sobre la isla 2 y has caminado una distancia de ~9+8+4+3 = 24~. La única isla que no has logrado visitar es la isla 4. Observa que al final del recorrido descrito arriba no puedes visitar ninguna isla. Dicho más precisamente:

o No eres capaz de visitarla caminando porque no existe un puente conectando a la isla 2 (donde te encuentras parado actualmente) y la isla 4.

o No eres capaz de visitarla usando una lancha, porque la isla 4 es alcanzable desde la isla 2, donde te encuentras parado actualmente. Una manera de alcanzarla es: Usa el puente ~(2-7)~, entonces usa la lancha que ya habias usado para ir desde la isla 7 hasta la isla 6, luego el puente ~(6-3)~, y finalmente el puente ~(3-4)~.