Una vez en un tiempo, en un pobre reino de Ragland, vivía un rey y una reina (de limosneros). Ellos tenían solo una hija, la encantadora Pauperella. Quien deseaba casarse el hermoso y deslumbrante príncipe rico Goldteeth. Aunque el joven príncipe protestaba, sus padres insistían que la boda debía realizarse en su castillo. Ellos le pidieron a su excelente cocinero que prepara los pasteles para la boda – los famosos pasteles de Ragland. Pero porque ellos si son tan buenos como se puede esperar (considerado que ellos son una pareja real), ellos solo tienen un cocinero y un pequeño horno, el en cual todos los pasteles tienen que ser horneado.

El cocinero tiene que preparar ~N~ pasteles diferentes. La preparación de un pastel consiste de dos etapas: en la primera etapa el cocinero prepara la masa para el pastel y le da forma. En la segunda etapa el pastel se hornea en el horno. Preparar la masa para el i-ésimo pastel toma ai segundos. Después que la masa está lista el pastel necesita ser horneado bi segundos. (Note que no tiene que ser horneado inmediatamente después de estar listo, la masa puede estar de esta forma mientras tanto). El cocinero es hábil preparando una masa en un momento. En cualquier momento cuando más un pastel puede hornearse en el horno. El cocinero puede preparar la masa de los pasteles en un orden arbitrario.

Su tarea es encontrar el tiempo mínimo necesitado para preparar todos los pasteles. Usted puede suponer que para la manipulación con el horno (es decir, insertando y sacando un pastel horneado del horno) puede ser realizado en 0 tiempo.

Entrada

La primera línea de la entrada estándar hay un entero positivo ~N \leq 1 000 000~ – el número de pasteles, el cual debe hacerse. Cada una de las siguientes ~N~ líneas contienen dos enteros positivos ~a_i, b_i \leq 2 000 000 000~, donde ~a_i~, es el tiempo necesitado para preparar la masa del i-ésimo pastel y ~b_i~ es el tiempo necesitado para ser horneado.

Salida

La salida estándar debe contener una sola línea con el mínimo tiempo, el cual todos los pasteles estén hechos. Usted puede asumir que su respuesta no excederá a 2 000 000 000.

Ejemplo de Entrada

5                   
1 10
7 1
5 4
15 15
30 1

Ejemplo de Salida

59

Explicación: una posible forma de cómo preparar todos los pasteles asignados en un tiempo óptimo:

Tiempo      Acción
0           comenzando la preparación del pastel #1                
1           #1 preparado, comenzando el horneo del #1, comenzando la preparación del #2    
8           #2 preparado, comenzando la preparación del #3    
11          #1 Terminado
13          #3 preparado,  comenzando la preparación del #4    
14             comenzando el horneo del #3
18          #3 terminado, comenzando el horno del #2
19          #2 terminado 
28          #4 preparado, comenzando el horno del #4, comienzo de la preparación del ·4
43          #4 terminado 
58          #2 preparado,  comenzando el horno del ·#5  
59          #5 terminado