Problem
Ghiaccio quiere caminar por las calles de Venecia. Sin embargo, hoy está bastante irritable, lo que le dificulta caminar.
Venecia es una ciudad bastante popular entre los turistas, quienes, sin embargo, llaman a la ciudad "Venecia" de manera extranjera, en lugar de la correcta "Venezia".
Esto enfada mucho a Ghiaccio, pero no quiere seguir furioso después del paseo. Por eso, decidió que a veces se tapaba los oídos al pasar junto a los turistas para no volver a enfadarse.
Ghiaccio tiene una barra de calma interna que se recarga en un punto por segundo (cuando Ghiaccio sale de casa, el valor de esta barra es cero).
Sin embargo, si Ghiaccio pasa junto a un grupo de turistas, en el que hay d personas, entonces su calma disminuye en d, porque se enoja por la mala pronunciación del nombre de la ciudad. Pero si Ghiaccio pasa tapándose los oídos, su tranquilidad no disminuirá.
Si en algún momento la escala de calma se vuelve negativa, entonces Ghiaccio se volverá loco, lo cual es extremadamente inaceptable.
Ghiaccio conoce muy bien Venecia, por lo que sabe que durante el paseo pasará unos n grupos de turistas, por cada uno de los cuales se sabe que estará en el segundo con el número t
i y en este grupo habrá d< sub>i personas.
Con base en esta información, calcula el número mínimo de veces que Ghiaccio tendrá que taparse los oídos para que no se vuelva loco mientras camina.
Entrada:
La primera línea contiene un único número entero n (1 ≤ n ≤ 200000) — el número de grupos de turistas por los que pasará Ghiaccio.
Luego siguen n líneas, cada una con dos enteros separados por espacios: t
i y d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — el número del segundo en el que Ghiaccio pasará por el i-ésimo grupo de turistas, y el número de personas en él. Todos los t
i son distintos y están en orden ascendente.
Salida:
Imprime un solo entero — el número mínimo de veces que Ghiaccio tendrá que taparse los oídos para no volverse loco.
Ejemplos:
| Entrada |
Salida |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Explicaciones:
En el primer ejemplo, Ghiaccio tiene que taparse los oídos al pasar cerca del segundo grupo.
Luego, al final del tercer segundo, su calma será igual a 1 (3 que compensó por cada segundo de la caminata, pero disminuyó en 2 al pasar por el primer grupo).
Al final del quinto segundo, la calma será igual a 3 (la calma no disminuirá a partir del segundo grupo, porque Ghiaccio se tapó los oídos al pasar).
Y al final del sexto segundo, la calma será igual a 3+1-3 = 1.
Además, su calma nunca disminuye.