Trawniki w Иннополис są koszone przez elektryczne roboty-kosiarki. Przyjmijmy, że trawnik jest odcinkiem osi liczbowej, na którym w pewnych punktach znajdują się roboty-kosiarki. Ich rozmiary można pominąć. Jeden robot stoi na początku trawnika (na lewo od niego nie ma trawnika), a jeden na jego końcu (na prawo od niego nie ma trawnika). Każdy robot jest początkowo skierowany w jednym z dwóch kierunków: w prawo albo w lewo.

Energia zgromadzona w $i$-tym robocie wystarcza na skoszenie $p_i$ metrów trawnika. Po nocnym ładowaniu wszystkie roboty zaczynają pracę jednocześnie i poruszają się z taką samą prędkością. Każdy robot jedzie po prostej w swoim kierunku. Robot zatrzymuje się w jednym z trzech przypadków:

1. Gdy wyczerpie mu się energia. Innymi słowy, gdy $i$-ty robot przejedzie $p_i$ metrów od punktu startu.
2. Gdy dojedzie do początku lub końca trawnika.
3. Gdy spotka w tym samym punkcie innego robota, który jechał mu naprzeciw albo zatrzymał się wcześniej w tym punkcie.

Przed uruchomieniem robotów możesz zmienić kierunek niektórych z nich na przeciwny. Należy skosić trawę na całym trawniku.

Wyznacz minimalną liczbę robotów, którym trzeba zmienić kierunek, aby ostatecznie cała trawa na trawniku została skoszona. W przeciwnym razie zgłoś, że skoszenie całej trawy jest niemożliwe.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2 \le n \le 10^5$), oznaczającą liczbę robotów.

Kolejnych $n$ wierszy zawiera opisy robotów w kolejności ich położenia na prostej od lewej do prawej. Każdego robota opisują trzy liczby całkowite $x_i$, $p_i$, $d_i$: jego początkowe położenie, liczba metrów, które może przejechać, oraz kierunek ruchu ($0=x_1<x_2<\ldots<x_n \le 10^9$, $1 \le p_i \le 10^9$; wartość $d_i=-1$ oznacza ruch w lewo, w kierunku malejącej współrzędnej, a $d_i=1$ oznacza ruch w prawo, w kierunku rosnącej współrzędnej). Początek i koniec trawnika znajdują się odpowiednio w punktach $x_1=0$ i $x_n$.

Wyjście

W jedynym wierszu wypisz $-1$, jeśli skoszenie całej trawy na trawniku jest niemożliwe. W przeciwnym razie wypisz jedną liczbę: liczbę robotów, którym należy zmienić kierunek na przeciwny, aby trawnik został skoszony.

Podzadania

Przykład

Wejście 1

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

Wyjście 1

1

Wejście 2

2
0 1 1
4 2 -1

Wyjście 2

-1

Uwagi

Pierwszy przykład przedstawiono na rysunku. Aby skosić całą trawę, można na przykład odwrócić robota stojącego pośrodku.