El pequeño D está preparando un viaje alrededor del mundo. Antes de partir, necesita completar según lo planeado las $n$ operaciones de preparación de suministros de su lista, las cuales están numeradas inicialmente en orden como $1, 2, \dots, n$.

Sea la cantidad actual de suministros el número entero $x$, siendo inicialmente $x = 0$. La $i$-ésima operación está descrita por dos enteros positivos $a_i, b_i$; al ejecutar dicha operación ocurren sucesivamente los siguientes cambios:

1. Primero se incrementa $x$ en $a_i$ (es decir, se hace $x \leftarrow x + a_i$);
2. A continuación se comprueba el tamaño de $x$: si en ese momento $x > b_i$, entonces se reduce $x$ hasta $b_i$ (es decir, se hace $x \leftarrow \min(x, b_i)$).

Antes de comenzar a ejecutar las operaciones, el pequeño D puede realizar a lo sumo un ajuste en el orden de la lista: elegir cualquiera de las operaciones, extraerla y moverla al final de la secuencia, manteniendo sin cambios el orden relativo del resto de las operaciones (también puede optar por no realizar ningún ajuste).

Una vez finalizado el ajuste, el pequeño D ejecutará en el nuevo orden, de principio a fin, todas las $n$ operaciones sucesivamente, ejecutando cada operación exactamente una vez. El pequeño D quiere saber: después de haber ejecutado todas las operaciones, ¿cuál es el máximo valor posible para la cantidad de suministros $x$?

Entrada

Leer los datos desde stdin.

La primera línea contiene un entero positivo $n$, que representa la cantidad de operaciones.

En las siguientes $n$ líneas, la $i$-ésima línea contiene dos enteros positivos $a_i, b_i$, que describen los parámetros de la $i$-ésima operación.

Salida

Escribir en stdout.

Imprimir una línea con un único entero, que representa el valor máximo posible de la cantidad de suministros $x$ tras haber ejecutado todas las operaciones.

Ejemplos

Entrada 1

3
1 100
100 90
1 1

Salida 1

90

Nota

Al mover la $2$-da operación al final de la secuencia, el orden de ejecución de las operaciones pasa a ser $1, 3, 2$. Después de ejecutar cada operación, el valor de $x$ pasa a ser sucesivamente $1, 1, 90$.

Si se mueve la $1$-ra operación al final, finalmente $x = 2$; si no se ajusta el orden o se mueve la $3$-ra operación al final, finalmente $x = 1$. Por lo tanto, el valor máximo posible de $x$ es $90$.

Ejemplo 2

Véanse supply/supply2.in y supply/supply2.ans en el directorio del concursante.

Este ejemplo satisface las restricciones de los casos de prueba $1 \sim 4$.

Ejemplo 3

Véanse supply/supply3.in y supply/supply3.ans en el directorio del concursante.

Este ejemplo satisface las restricciones de los casos de prueba $5 \sim 6$.

Ejemplo 4

Véanse supply/supply4.in y supply/supply4.ans en el directorio del concursante.

Este ejemplo satisface las restricciones de los casos de prueba $7 \sim 10$.

Restricciones

Para todos los datos, se garantiza que $1 \le n \le 2 \times 10^5$ y $1 \le a_i, b_i \le 10^9$. Tenga en cuenta que: los datos no garantizan que $a_i \le b_i$.

Este problema tiene un total de $10$ casos de prueba, cada uno vale $10$ puntos, y cada caso de prueba se califica de manera independiente. Los rangos detallados de los datos se muestran en la siguiente tabla.

Propiedad especial A: $b_1 = b_2 = \dots = b_n$.