[116A] Tranvía

Enlace a Codeforces

El Reino Lineal tiene exactamente una línea de tranvía. Esta tiene $n$ paradas, numeradas del $1$ al $n$ en el orden del movimiento del tranvía. En la parada i-ésima, $a_i$ pasajeros se bajan del tranvía, mientras que $b_i$ pasajeros ingresan en él. El tranvía está vacío antes de que llegue a la primera parada. Además, cuando el tranvía llega a la última parada, todos los pasajeros se bajan de modo que se vacía.

Tu tarea es calcular la capacidad mínima del tranvía de tal forma que el número de personas dentro del tranvía en cualquier momento nunca exceda esta capacidad. Nota que en cada parada todos los pasajeros que se bajan, lo hacen antes de que cualquier otro pasajero se suba al tranvía.

Entrada

La primera línea contiene un único número $n$ ($2 \leq n \leq 1000$) - el número de paradas del tranvía.

Las $n$ líneas que siguen, cada una contiene dos enteros $a_i$ y $b_i$ ($0 \leq a_i, b_i \leq 1000$) - el número de pasajeros que se baja del tranvía en la i-ésima parada, y el número de pasajeros que se suba al tranvía en la i-ésima parada. Las paradas se dan desde la primera a la última en el orden del movimiento del tranvía.

• El número de personas que se bajan en una determinada parada no excede al total de personas en el tranvía inmediatamente antes de que llegue a la parada. De modo más formal, $\displaystyle \forall i (1\leq i \leq n) : \sum_{j = 1}^{i - 1} b_j - \sum_{j = 1}^{i - 1} a_j \geq a_i$. En particular, esto significa que $a_1 = 0$.

• En la última parada, todos los pasajeros se bajan del tranvía y se vacía. De modo más formal, $\displaystyle \sum_{j=1}^{n-1} b_j - \sum_{j=1}^{n-1} a_j = a_n$.

• Ningún pasajero se subirá al tranvía en la última parada. Es decir, $b_n = 0$.

Salida

Imprime un entero indicando la capacidad mínima posible del tranvía (el 0 está permitido)

Ejemplos

input:
4
0 3
2 5
4 2
4 0

output:
6

Nota

Para el primer ejemplo, una capacidad de 6 es suficiente:

• En la primera parada, el número de pasajeros dentro del tranvía es 0. Luego, se suben 3 pasajeros, y número de pasajeros dentro del tranvía se hace 3.

• En la segunda para, 2 pasajeros se bajan (1 pasajero queda dentro). Luego, 5 pasajeros se suben al tranvía. Hay 6 pasajeros dentro del tranvía ahora.

• En la tercera parada, 4 pasajeros se bajan (2 quedan adentro). Luego, 2 pasajeros se suben al tranvía. Hay 4 pasajero dentro del tranvía ahora.

• Finalmente, todos los pasajeros restantes se bajan en la última parada. No hay pasajeros dentro del tranvía ahora, lo cual está en línea con las condiciones.

Dado que el número de pasajero dentro del tranvía nunca excede a 6, una capacidad de 6 es suficiente. Adicionalmente, no es posible para el tranvía tener una capacidad menor a 6. Por lo tanto, 6 es la respuesta correcta.