En Иннополис, robots cortacésped eléctricos cortan los céspedes. Consideraremos que un césped es un segmento de la recta numérica en algunos de cuyos puntos hay robots cortacésped. El tamaño de los robots puede despreciarse. Uno de los robots se encuentra al principio del césped (no hay césped a su izquierda) y otro al final (no hay césped a su derecha). Inicialmente, cada robot está orientado en una de dos direcciones: hacia la derecha o hacia la izquierda.
La carga del robot $i$ le permite cortar $p_i$ metros de césped. Después de cargarse durante la noche, todos los robots empiezan a trabajar simultáneamente y se mueven a la misma velocidad. Cada robot avanza en su dirección a lo largo de la recta. Un robot se detiene en uno de estos tres casos:
- Si se queda sin carga. En otras palabras, si el robot $i$ ha recorrido $p_i$ metros desde su punto de partida.
- Si llega al principio o al final del césped.
- Si se encuentra en un mismo punto con otro robot que se movía hacia él o que se había detenido antes en ese punto.
Antes de poner los robots en marcha, puedes invertir la dirección de algunos de ellos. Es necesario cortar la hierba de todo el césped.
Determina el número mínimo de robots cuya dirección debe invertirse para que, al final, toda la hierba del césped quede cortada. Si no es posible, indica que no se puede cortar toda la hierba.
Entrada
La primera línea contiene un entero $n$ $(2\le n\le10^5)$: el número de robots.
Las siguientes $n$ líneas contienen las descripciones de los robots en el orden en que se encuentran en la recta, de izquierda a derecha. Cada robot se caracteriza por tres enteros $x_i,p_i,d_i$: su posición inicial, el número de metros que puede recorrer y su dirección de movimiento ($0=x_1<x_2<\ldots<x_n\le10^9,\ 1\le p_i\le10^9$; $d_i=-1$ indica movimiento hacia la izquierda, en la dirección de coordenadas decrecientes, y $d_i=1$ indica movimiento hacia la derecha, en la dirección de coordenadas crecientes). El principio y el final del césped están en los puntos $x_1=0$ y $x_n$, respectivamente.
Salida
En una única línea, imprime $-1$ si no es posible cortar toda la hierba del césped. En caso contrario, imprime un número: la cantidad de robots cuya dirección hay que invertir para cortar el césped.
Subtareas
| Subtarea | Puntos | Restricciones sobre $n$ | Restricciones adicionales | Subtareas necesarias |
|---|---|---|---|---|
| $1$ | $23$ | $n\le10$ | Ejemplos | |
| $2$ | $16$ | Inicialmente todos los robots están orientados hacia la derecha ($d_i=1$) | ||
| $3$ | $17$ | $n\le1000$ | Ejemplos, $1$ | |
| $4$ | $13$ | $x_i=i-1,\ p_i=1$ | ||
| $5$ | $14$ | $p_i=10^9$ | ||
| $6$ | $17$ | Sin restricciones adicionales | Ejemplos, $1$–$5$ |
Ejemplos
Entrada 1
3 0 1 -1 1 1 1 2 1 -1
Salida 1
1
Entrada 2
2 0 1 1 4 2 -1
Salida 2
-1
Nota
El primer ejemplo está representado en la figura. Para cortar toda la hierba, se puede, por ejemplo, invertir la dirección del robot situado en el centro.