Les pelouses d'Иннополис sont tondues par des robots tondeuses électriques. Nous considérerons qu'une pelouse est un segment de la droite numérique, sur lequel des robots tondeuses se trouvent en certains points. La taille des robots peut être négligée. Un robot se trouve au début de la pelouse (il n'y a pas de pelouse à sa gauche), et un autre à la fin (il n'y a pas de pelouse à sa droite). Chaque robot est initialement orienté dans l'une de deux directions : vers la droite ou vers la gauche.
La charge du robot $i$ suffit pour tondre $p_i$ mètres de pelouse. Après leur recharge nocturne, tous les robots commencent à travailler simultanément et se déplacent à la même vitesse. Chaque robot se déplace dans sa propre direction le long de la droite. Un robot s'arrête dans l'un des trois cas suivants :
- Sa charge est épuisée. Autrement dit, le robot $i$ a parcouru $p_i$ mètres depuis son point de départ.
- Il atteint le début ou la fin de la pelouse.
- Il rencontre, en un même point, un autre robot qui se déplaçait à sa rencontre ou s'était auparavant arrêté en ce point.
Avant de démarrer les robots, vous pouvez inverser la direction de certains d'entre eux. Il faut tondre l'herbe sur toute la pelouse.
Déterminez le nombre minimal de robots dont il faut inverser la direction pour que toute l'herbe de la pelouse soit finalement tondue. Sinon, indiquez qu'il est impossible de tout tondre.
Entrée
La première ligne contient un entier $n$ ($2\le n\le 10^5$), le nombre de robots.
Les $n$ lignes suivantes décrivent les robots dans l'ordre de leur position sur la droite, de gauche à droite. Chaque robot est caractérisé par trois entiers $x_i,p_i,d_i$ : sa position initiale, le nombre de mètres qu'il peut parcourir et sa direction de déplacement ($0=x_1<x_2<\cdots<x_n\le 10^9$, $1\le p_i\le 10^9$ ; $d_i=-1$ indique un déplacement vers la gauche, dans le sens des coordonnées décroissantes, et $d_i=1$ indique un déplacement vers la droite, dans le sens des coordonnées croissantes). Le début et la fin de la pelouse se trouvent respectivement aux points $x_1=0$ et $x_n$.
Sortie
Sur une seule ligne, affichez $-1$ s'il est impossible de tondre toute l'herbe de la pelouse. Sinon, affichez un nombre : le nombre de robots dont il faut inverser la direction pour tondre la pelouse.
Sous-tâches
| Sous-tâche | Points | Contrainte sur $n$ | Contraintes supplémentaires | Sous-tâches requises |
|---|---|---|---|---|
| $1$ | $23$ | $n\le 10$ | Exemples | |
| $2$ | $16$ | Tous les robots sont initialement orientés vers la droite ($d_i=1$). | ||
| $3$ | $17$ | $n\le 1000$ | Exemples, $1$ | |
| $4$ | $13$ | $x_i=i-1$, $p_i=1$ | ||
| $5$ | $14$ | $p_i=10^9$ | ||
| $6$ | $17$ | Aucune contrainte supplémentaire | Exemples, $1$–$5$ |
Exemples
Entrée 1
3 0 1 -1 1 1 1 2 1 -1
Sortie 1
1
Entrée 2
2 0 1 1 4 2 -1
Sortie 2
-1
Remarque
Le premier exemple est représenté sur la figure. Pour tondre toute l'herbe, on peut, par exemple, retourner le robot situé au milieu.