El Granjero Juan se ha dado cuenta que sus vacas son más fáciles de ordeñar cuando tienen otra vaca cercana por apoyo moral. El por lo tanto quiere tomar sus ~M~ vacas y partirlas en ~M/2~ pares. Cada par de vacas será guiada a un establo separado en la granja para ordeño. El ordeño en cada una de esos ~M/2~ establos será simultaneo.

Para hacer las cosas un poco más complicadas, cada una de las vacas del Granjero Juan tiene una producción diferente de leche. Si las vacas con producciones ~A~ y ~B~ son puestas en el mismo par, entonces se requiere ~A+B~ unidades de tiempo para ordeñar a las dos.

Por favor ayude al Granjero Juan a determinar la cantidad mínima posible de tiempo para que todo el proceso de ordeño se termine, asumiendo que el forme los pares de vacas de la mejor manera posible.

Entrada

La primera línea de la entrada contiene a ~N~. Cada una de las siguientes ~N~ líneas contiene dos enteros ~x~ y ~y~, indicando que GJ tiene ~x~ vacas con producción de leche ~y~. La suma de los x's es ~M~, el número total de vacas.

Salida

Imprima la cantidad mínima de tiempo que le toma a GJ para que sus vacas sean ordeñadas, asumiendo que están emparejadas de manera óptima.

Restricciones

• ~M \leq 1,000,000,000, M par~
• ~1 \leq N \leq 100,000~
• ~1 \leq y \leq 1,000,000,000~

Ejemplo de Entrada

3
1 8
2 5
1 2

Ejemplo de Salida

10

Aquí, si las vacas con producciones ~8+2~ están en el mismo par, y esas con producciones 5+5 están en el mismo par, en ambos establos se demora el ordeño 10 unidades. Como el ordeño ocurre de manera simultánea, todo el proceso debería por lo tanto completarse en 10 unidades de tiempo. Cualquier otra manera de formar los pares sería sub-óptima, resultando en que un establo demoraría más de 10 unidades de tiempo para ordeñar.

USACO 2017 US Open Contest, Silver Problem 1. Paired Up.