Die Rasenflächen in Иннополис werden von elektrischen Mährobotern gemäht. Wir nehmen an, dass eine Rasenfläche ein Intervall auf der Zahlengeraden ist, an dessen Punkten einige Mähroboter stehen. Die Größe der Roboter kann vernachlässigt werden. Ein Roboter steht am Anfang der Rasenfläche (links davon gibt es keinen Rasen), und einer am Ende (rechts davon gibt es keinen Rasen). Jeder Roboter ist anfangs in eine von zwei Richtungen ausgerichtet: nach rechts oder nach links.
Die Akkuladung des $i$-ten Roboters reicht aus, um $p_i$ Meter Rasen zu bearbeiten. Nach dem nächtlichen Aufladen beginnen alle Roboter gleichzeitig zu arbeiten und bewegen sich mit derselben Geschwindigkeit. Jeder Roboter bewegt sich entlang der Geraden in seiner Richtung. Ein Roboter hält in einem der folgenden drei Fälle an:
- Wenn seine Akkuladung aufgebraucht ist. Anders gesagt: wenn der $i$-te Roboter $p_i$ Meter von seinem Startpunkt aus zurückgelegt hat.
- Wenn er den Anfang oder das Ende der Rasenfläche erreicht hat.
- Wenn er an einem Punkt auf einen anderen Roboter trifft, der ihm entgegengefahren ist oder bereits zuvor an diesem Punkt angehalten hat.
Bevor die Roboter gestartet werden, können Sie die Richtung einiger Roboter umkehren. Das Gras auf der gesamten Rasenfläche muss gemäht werden.
Bestimmen Sie die minimale Anzahl von Robotern, deren Richtung umgekehrt werden muss, damit am Ende das gesamte Gras auf der Rasenfläche gemäht ist. Andernfalls geben Sie an, dass es unmöglich ist, das gesamte Gras zu mähen.
Eingabe
Die erste Zeile enthält eine ganze Zahl $n$ ($2\le n\le10^5$), die Anzahl der Roboter.
Die folgenden $n$ Zeilen beschreiben die Roboter in der Reihenfolge ihrer Positionen auf der Geraden von links nach rechts. Jeder Roboter wird durch drei ganze Zahlen $x_i,p_i,d_i$ beschrieben: seine Anfangsposition, die Anzahl der Meter, die er zurücklegen kann, und seine Bewegungsrichtung ($0=x_1<x_2<\cdots<x_n\le10^9$, $1\le p_i\le10^9$; $d_i=-1$ bedeutet Bewegung nach links, in Richtung abnehmender Koordinaten, und $d_i=1$ bedeutet Bewegung nach rechts, in Richtung zunehmender Koordinaten). Der Anfang und das Ende der Rasenfläche liegen bei $x_1=0$ beziehungsweise $x_n$.
Ausgabe
Geben Sie in einer einzigen Zeile $-1$ aus, wenn es unmöglich ist, das gesamte Gras auf der Rasenfläche zu mähen. Andernfalls geben Sie eine Zahl aus: die Anzahl der Roboter, deren Richtung umgekehrt werden muss, damit die Rasenfläche gemäht wird.
Teilaufgaben
| Teilaufgabe | Punkte | Beschränkungen für $n$ | Zusätzliche Beschränkungen | Benötigte Teilaufgaben |
|---|---|---|---|---|
| $1$ | $23$ | $n\le10$ | Beispiele | |
| $2$ | $16$ | Anfangs sind alle Roboter nach rechts ausgerichtet ($d_i=1$) | ||
| $3$ | $17$ | $n\le1000$ | Beispiele, $1$ | |
| $4$ | $13$ | $x_i=i-1$, $p_i=1$ | ||
| $5$ | $14$ | $p_i=10^9$ | ||
| $6$ | $17$ | Keine zusätzlichen Beschränkungen | Beispiele, $1$–$5$ |
Beispiele
Eingabe 1
3 0 1 -1 1 1 1 2 1 -1
Ausgabe 1
1
Eingabe 2
2 0 1 1 4 2 -1
Ausgabe 2
-1
Hinweis
Das erste Beispiel ist in der Abbildung dargestellt. Um das gesamte Gras zu mähen, kann man beispielsweise den Roboter in der Mitte umdrehen.