Electric lawnmower robots mow lawns in Innopolis. We can assume that the lawn is a segment of a number line on which robots are located at certain points. The size of the robots can be neglected. One robot is at the beginning of the lawn (there is no lawn to its left), and one is at the end (there is no lawn to its right). Each robot is initially oriented in one of two directions: either to the right or to the left.

The charge of the $i$-th robot is sufficient to process $p_i$ meters of lawn. After charging overnight, all robots start working simultaneously and move at the same speed. Each robot moves in its direction along the line. A robot stops in one of three cases:

1. If the robot runs out of charge. In other words, if the $i$-th robot has traveled $p_i$ meters from its starting point.
2. If the robot reaches the beginning or the end of the lawn.
3. If the robot meets another robot at a point that was moving towards it or had stopped at this point earlier.

Before starting the robots, you can change the direction of some of them to the opposite. It is required to mow the grass on the entire lawn.

Determine the minimum number of robots whose direction needs to be changed so that all the grass on the lawn is mowed. Otherwise, report that it is impossible to mow all the grass.

Input

The first line contains an integer $n$ ($2 \leqslant n \leqslant 10^5$) — the number of robots.

The next $n$ lines contain descriptions of the robots in the order of their position on the line from left to right. Each robot is characterized by three integers $x_i, p_i, d_i$: its initial position, the number of meters it can travel, and its direction of movement ($0 = x_1 < x_2 < \dots < x_n \leqslant 10^9$, $1 \leqslant p_i \leqslant 10^9$, the value $d_i = 1$ denotes movement to the left, in the direction of decreasing coordinates, $d_i = -1$ denotes movement to the right, in the direction of increasing coordinates). The beginning and end of the lawn are at points $x_1 = 0$ and $x_n$ respectively.

Output

In a single line, output $-1$ if it is impossible to mow all the grass on the lawn. Otherwise, output a single number — the minimum number of robots whose direction needs to be changed to the opposite so that the lawn is mowed.

Subtasks

Examples

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

Note

The first example is shown in the figure. To mow all the grass, you can, for example, turn around the robot that is in the middle.