Os relvados de Иннополис são cortados por robôs corta-relva elétricos. Suponha que um relvado é um segmento de uma reta numérica, com robôs corta-relva em alguns dos seus pontos. O tamanho dos robôs pode ser desprezado. Um dos robôs está no início do relvado (não há relvado à sua esquerda) e outro no fim (não há relvado à sua direita). Cada robô está inicialmente orientado numa de duas direções: para a direita ou para a esquerda.
A carga do $i$-ésimo robô permite cortar $p_i$ metros de relvado. Após carregarem durante a noite, todos os robôs começam a trabalhar simultaneamente e deslocam-se à mesma velocidade. Cada robô move-se na sua direção ao longo da reta. Um robô para numa das três situações seguintes:
- Se a sua carga acabar. Por outras palavras, se o $i$-ésimo robô tiver percorrido $p_i$ metros desde o ponto de partida.
- Se chegar ao início ou ao fim do relvado.
- Se se encontrar no mesmo ponto que outro robô que se movia na sua direção em sentido contrário ou que já tinha parado nesse ponto.
Antes de iniciar os robôs, pode inverter a direção de alguns deles. É necessário cortar toda a relva do relvado.
Determine o número mínimo de robôs cuja direção deve ser invertida para que, no final, toda a relva tenha sido cortada. Caso contrário, indique que é impossível cortar toda a relva.
Entrada
A primeira linha contém um inteiro $n$ ($2\le n\le 10^5$): o número de robôs.
As $n$ linhas seguintes descrevem os robôs pela ordem das suas posições na reta, da esquerda para a direita. Cada robô é caracterizado por três inteiros $x_i,p_i,d_i$: a posição inicial, o número de metros que pode percorrer e a direção do movimento ($0=x_1<x_2<\cdots<x_n\le 10^9$, $1\le p_i\le 10^9$; $d_i=-1$ indica movimento para a esquerda, no sentido de coordenadas decrescentes, e $d_i=1$ indica movimento para a direita, no sentido de coordenadas crescentes). O início e o fim do relvado estão nos pontos $x_1=0$ e $x_n$, respetivamente.
Saída
Na única linha, imprima $-1$ se for impossível cortar toda a relva do relvado. Caso contrário, imprima um número: a quantidade de robôs cuja direção deve ser invertida para que o relvado seja cortado.
Subtarefas
| Subtarefa | Pontos | Restrições sobre $n$ | Restrições adicionais | Subtarefas necessárias |
|---|---|---|---|---|
| $1$ | $23$ | $n\le 10$ | Exemplos | |
| $2$ | $16$ | Inicialmente, todos os robôs estão orientados para a direita ($d_i=1$) | ||
| $3$ | $17$ | $n\le 1000$ | Exemplos, $1$ | |
| $4$ | $13$ | $x_i=i-1$, $p_i=1$ | ||
| $5$ | $14$ | $p_i=10^9$ | ||
| $6$ | $17$ | Sem restrições adicionais | Exemplos, $1$–$5$ |
Exemplos
Entrada 1
3 0 1 -1 1 1 1 2 1 -1
Saída 1
1
Entrada 2
2 0 1 1 4 2 -1
Saída 2
-1
Nota
O primeiro exemplo está representado na figura. Para cortar toda a relva, pode-se, por exemplo, inverter a direção do robô que está no meio.