Convención II#10397
A pesar de las largas demoras en las recogidas en el aeropuerto, la convención de Farmer John para vacas interesadas en comer pasto ha ido bien hasta ahora. Ha atraído vacas de todas partes del mundo.
Sin embargo, el evento principal de la convención parece que podría causarle a Farmer John más problemas de programación. Un pastizal muy pequeño en su granja presenta un tipo raro de pasto que, según vacas exigentes, es el más sabroso del mundo. Como resultado, las vacas que asisten a la convención quieren probar este pasto. Esto probablemente generará largas filas, ya que el pastizal es tan pequeño que solo puede acomodar a una vaca a la vez.
Farmer John conoce el momento a_i en que cada vaca planea llegar al pastizal especial, así como la cantidad de tiempo t_i que planea pasar comiendo el pasto una vez que le llegue su turno. Una vez que la vaca comienza a comer, permanece durante las t_i unidades de tiempo completas antes de irse, y durante este tiempo las demás vacas que lleguen deben esperar. Si varias vacas están esperando cuando el pastizal vuelve a quedar libre, la vaca con mayor antigüedad puede probar el pasto a continuación. Para este propósito, se considera que una vaca que llega exactamente cuando otra vaca termina de comer está esperando. De manera similar, si varias vacas llegan exactamente al mismo tiempo mientras ninguna vaca está comiendo, la que tenga mayor antigüedad come a continuación.
Ayuda a FJ a calcular el tiempo máximo que cualquier vaca tiene que esperar en la fila (entre su momento de llegada a_i y el momento en que comienza a comer).
La primera línea contiene un entero n~(1 \le n \le 10^5). Cada una de las siguientes líneas describe a una vaca y contiene dos enteros a_i y t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4). Las vacas están listadas en orden de antigüedad, comenzando con la más antigua.
Imprime un entero — el tiempo máximo de espera entre todas las vacas.
Ejemplo 1
En este ejemplo, hay vacas, numeradas en el orden en que aparecen en la entrada. La vaca llega primero (en el tiempo ), y antes de que termine de comer (en el tiempo ), llegan las vacas y . Como la vaca tiene mayor antigüedad, come a continuación, habiendo esperado unidades de tiempo desde su llegada. Termina en el tiempo , y luego la vaca comienza a comer, habiendo esperado unidades de tiempo desde su llegada. Después de un período en el que ninguna vaca está comiendo, llega la vaca , y mientras está comiendo, llega la vaca ; la vaca comienza a comer unidades de tiempo después de su llegada. Así, la vaca que espera más tiempo es la vaca .