Problem
Ghiaccio veut se promener dans les rues de Venise. Cependant, aujourd'hui, il est assez irritable, ce qui le rend difficile à marcher.
Venise est une ville assez populaire parmi les touristes, qui, cependant, appellent la ville "Venise" d'une manière étrangère, au lieu de la bonne "Venezia".
Cela rend Ghiaccio très en colère, mais il ne veut pas rester furieux après la promenade. Par conséquent, il a décidé que parfois il se boucherait les oreilles en passant devant des touristes pour ne plus se fâcher.
Ghiaccio a une barre de calme interne qui se reconstitue d'un point par seconde (lorsque Ghiaccio quitte la maison, la valeur de cette barre est zéro).
Cependant, si Ghiaccio passe devant un groupe de touristes, dans lequel il y a d personnes, alors son calme diminue de d, car il se met en colère contre la mauvaise prononciation du nom de la ville. Mais si Ghiaccio passe par là en se bouchant les oreilles, son calme ne diminuera pas.
Si à un moment donné l'échelle de calme devient négative, alors Ghiaccio deviendra fou, ce qui est extrêmement inacceptable.
Ghiaccio connaît très bien Venise, il sait donc que pendant la promenade il croisera environ n groupes de touristes, pour chacun desquels on sait qu'il sera dans le second avec le numéro t
i et dans ce groupe il y aura d< sub>i personnes.
Sur la base de ces informations, calculez le nombre minimum de fois où Ghiaccio devra se boucher les oreilles pour ne pas devenir fou en marchant.
Saisie :
La première ligne contient un seul entier n (1 ≤ n ≤ 200000) — le nombre de groupes de touristes autour desquels passera Ghiaccio.
Viennent ensuite n lignes, chacune contenant deux entiers séparés par des espaces : t
i et d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) &mdash ; le numéro de la seconde au cours de laquelle Ghiaccio passera par le i-ème groupe de touristes, et le nombre de personnes qu'il contient. Tous les t
i sont distincts et classés par ordre croissant.
Sortie :
Imprimer un seul entier — le nombre minimum de fois où Ghiaccio devra se boucher les oreilles pour ne pas devenir fou.
Exemples :
| Entrée |
Sortie |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Explications :
Dans le premier exemple, Ghiaccio doit se boucher les oreilles en passant près du second groupe.
Puis à la fin de la troisième seconde, son calme sera égal à 1 (3 qu'il a rattrapé pour chaque seconde de marche, mais diminué de 2 en passant par le premier groupe).
A la fin de la cinquième seconde, le calme sera égal à 3 (le calme ne diminuera pas à partir du deuxième groupe, car Ghiaccio s'est bouché les oreilles en passant).
Et à la fin de la sixième seconde, le calme sera égal à 3+1-3 = 1.
De plus, son calme ne diminue jamais.