Иннополис의 잔디밭은 전기 잔디 깎기 로봇들이 깎는다. 잔디밭은 수직선 위의 선분이며, 그 위의 몇몇 지점에 잔디 깎기 로봇들이 놓여 있다고 하자. 로봇의 크기는 무시할 수 있다. 로봇 하나는 잔디밭의 시작점에 있고, 그보다 왼쪽에는 잔디밭이 없다. 또 다른 로봇 하나는 잔디밭의 끝점에 있고, 그보다 오른쪽에는 잔디밭이 없다. 각 로봇은 처음에 오른쪽 또는 왼쪽 중 한 방향을 향하고 있다.

$i$번째 로봇의 배터리는 잔디밭 $p_i$미터를 깎을 만큼 충전되어 있다. 밤 동안 충전한 뒤, 모든 로봇은 동시에 작업을 시작하고 같은 속도로 움직인다. 각 로봇은 수직선을 따라 자신이 향한 방향으로 움직인다. 로봇은 다음 세 경우 중 하나에 해당하면 멈춘다.

1. 배터리가 다 소모된 경우. 즉, $i$번째 로봇이 출발점에서 $p_i$미터를 이동한 경우이다.
2. 잔디밭의 시작점 또는 끝점에 도달한 경우.
3. 반대 방향에서 다가오던 다른 로봇, 또는 그 지점에서 이미 멈춘 다른 로봇과 같은 지점에서 만난 경우.

로봇들을 작동시키기 전에 일부 로봇의 방향을 반대로 바꿀 수 있다. 잔디밭 전체의 잔디를 깎아야 한다.

최종적으로 잔디밭의 모든 잔디가 깎이도록 하려면 최소 몇 대의 로봇의 방향을 바꿔야 하는지 구하여라. 모든 잔디를 깎는 것이 불가능하다면 그 사실을 알려라.

입력

첫 번째 줄에는 로봇의 수인 정수 $n$이 주어진다 ($2 \le n \le 10^5$).

다음 $n$개의 줄에는 로봇들이 수직선 위에 놓인 순서대로, 왼쪽부터 오른쪽으로 로봇의 정보가 주어진다. 각 로봇은 세 정수 $x_i,p_i,d_i$로 표현되며, 각각 시작 위치, 이동할 수 있는 거리(미터), 이동 방향을 나타낸다. $0=x_1<x_2<\cdots<x_n \le 10^9$이고 $1 \le p_i \le 10^9$이다. $d_i=-1$은 좌표가 감소하는 왼쪽 방향의 이동을, $d_i=1$은 좌표가 증가하는 오른쪽 방향의 이동을 뜻한다. 잔디밭의 시작점과 끝점은 각각 $x_1=0$과 $x_n$이다.

출력

잔디밭의 모든 잔디를 깎을 수 없다면 한 줄에 $-1$을 출력한다. 그렇지 않다면 잔디밭을 모두 깎기 위해 방향을 반대로 바꿔야 하는 로봇의 수를 하나의 수로 출력한다.

서브태스크

예제

입력 1

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

출력 1

1

입력 2

2
0 1 1
4 2 -1

출력 2

-1

참고

첫 번째 예제는 그림에 나타나 있다. 모든 잔디를 깎으려면, 예를 들어 가운데에 있는 로봇의 방향을 반대로 바꾸면 된다.