I prati di Иннополис vengono tagliati da robot tagliaerba elettrici. Consideriamo un prato come un segmento della retta numerica, con robot tagliaerba collocati in alcuni suoi punti. Le dimensioni dei robot possono essere trascurate. Un robot si trova all'inizio del prato (alla sua sinistra non c'è prato) e uno alla fine (alla sua destra non c'è prato). Ogni robot è inizialmente orientato in una delle due direzioni: verso destra o verso sinistra.

La carica del robot $i$ è sufficiente per tagliare $p_i$ metri di prato. Dopo la ricarica notturna, tutti i robot iniziano a lavorare contemporaneamente e si muovono alla stessa velocità. Ogni robot si muove lungo la retta nella propria direzione. Un robot si ferma in uno dei seguenti tre casi:

1. La sua carica si esaurisce. In altre parole, il robot $i$ ha percorso $p_i$ metri dal punto di partenza.
2. Raggiunge l'inizio o la fine del prato.
3. Incontra nello stesso punto un altro robot che si muoveva verso di lui oppure che si era già fermato in quel punto.

Prima di avviare i robot, potete invertire la direzione di alcuni di essi. È necessario tagliare l'erba su tutto il prato.

Determinate il numero minimo di robot a cui bisogna invertire la direzione affinché, alla fine, tutta l'erba del prato sia tagliata. Se ciò non è possibile, segnalate che non si può tagliare tutta l'erba.

Input

La prima riga contiene un intero $n$ ($2 \le n \le 10^5$), il numero di robot.

Le successive $n$ righe descrivono i robot nell'ordine in cui sono collocati sulla retta da sinistra a destra. Ogni robot è caratterizzato da tre interi $x_i,p_i,d_i$: la posizione iniziale, il numero di metri che può percorrere e la direzione di movimento ($0=x_1<x_2<\cdots<x_n \le 10^9$, $1 \le p_i \le 10^9$; $d_i=-1$ indica il movimento verso sinistra, nella direzione delle coordinate decrescenti, mentre $d_i=1$ indica il movimento verso destra, nella direzione delle coordinate crescenti). L'inizio e la fine del prato si trovano rispettivamente nei punti $x_1=0$ e $x_n$.

Output

Nell'unica riga, stampate $-1$ se non è possibile tagliare tutta l'erba del prato. Altrimenti, stampate un solo numero: il numero di robot a cui bisogna invertire la direzione affinché il prato sia tagliato.

Sottoproblemi

Esempi

Input 1

3
0 1 -1
1 1 1
2 1 -1

Output 1

1

Input 2

2
0 1 1
4 2 -1

Output 2

-1

Spiegazione

Il primo esempio è mostrato nella figura. Per tagliare tutta l'erba, si può, per esempio, invertire la direzione del robot che si trova al centro.