Aparte de los grandes atrasos en las recogidas del aeropuerto, la convención del Granjero Juan para vacas interesadas en comer pasto hasta ahora ha ido bien. Ha atraido vacas de todo el mundo.

Sin embargo, el evento principal de la conferencia, podría causar al Granjero Juan algunos problemas más de programación. Una pequeña parcela en su granja posee una forma rara de pasto que se supone ser la más sabrosa en el mundo, de acuerdo a las vacas conocedoras. Como resultado, todas las ~N~ vacas en la conferencia ~(1 \leq N \leq 10^5)~ quieren probar este pasto. Esto causará que se formen grandes filas, desde que la parcela es tan pequeña que solamente puede albergar una vaca al tiempo.

El Granjero Juan sabe el tiempo ~a_i~ en cada vaca ~i~ planea llegar a la parcela especial, así como la cantidad de tiempo ~t_i~ que ella planea gastar probando el pasto especial, una vez que su turno comience. Una vez que la vaca ~i~ comience a comer el pasto, ella usa todo su tiempo ~t_i~ antes de dejar la parcela, durante el cual otras vacas que lleguen necesitan esperar. Si varias vacas están esperando cuando la parcela vuelva a estar disponible, la vaca con mayor edad es la siguiente que se permite probar el pasto. Para este propósito una vaca que llegue justo en el memento en que otra vaca está finalizando se considera "esperando". De manera similar, si un número de vacas todas llegan al mismo tiempo cuando ninguna vaca está comiendo actualmente, entonces la de mayor edad será la próxima que va a comer.

Por favor ayude a GJ a calcular la cantidad máxima de tiempo que cualquier vaca tendría que esperar en la fila (entre el tiempo ~a_i~ y en el tiempo en que la vaca comience a comer).

Entrada

La primera línea de la entrada contiene ~N~. Cada una de las siguientes ~N~ líneas especifican los detalles de las ~N~ vacas en orden de edad (la vaca mayor siendo la primera). Cada línea contiene ~a_i~ y ~t_i~ para una vaca. Los ~t_i~ son enteros positivos cada uno a lo más ~10^4~, y los ~a_i~ son enteros positivos a lo más ~10^9~.

Salida

Por favor el tiempo potencialmente más largo de tiempo de espera entre todas las vacas.

Ejemplo de Entrada

5
25 3
105 30
20 50
10 17
100 10

Ejemplo de Salida

10

En este ejemplo, tenemos 5 vacas (numeradas 1..5 de acuerdo a su orden en la entada). La vaca 4 es la primera que llega (en tiempo 10), y antes de que ella pueda terminar de comer (en el tiempo 27) llegan ambas las vacas 1 y 3. Como la vaca 1 es mayor, ella es la siguiente, habiendo esperado 2 unidades de teimpo después de su tiempo de llegada. Ella termina en el tiempo 30, y entonces la vaca 3 empieza a comer, habiendo esperado 10 unidades de tiempo después del tiempo en que comenzó a comer. Después de un intervalo en que ninguna vaca come, la vaca 5 llega y luego mientras está comiendo llega la vaca 2, comiendo 5 unidades de tiempo después. La vaca que duró más esperando relativamente a su tiempo de llegada es la vaca 3.

USACO 2018 December Contest, Silver Problem 2. Convention II.