The lawns in Иннополис are mowed by electric robotic lawnmowers. We will regard a lawn as a segment of the number line, with robotic lawnmowers located at certain points on it. The sizes of the robots can be ignored. One robot stands at the beginning of the lawn (there is no lawn to its left), and one at the end (there is no lawn to its right). Each robot is initially facing one of two directions: either right or left.
The charge of robot $i$ is sufficient to mow $p_i$ meters of lawn. After charging overnight, all robots start working simultaneously and move at the same speed. Each robot moves along the line in its own direction. A robot stops in one of three cases:
- Its charge runs out. In other words, robot $i$ has traveled $p_i$ meters from its starting point.
- It reaches the beginning or the end of the lawn.
- It meets another robot at the same point, where that other robot was moving towards it or had stopped at that point earlier.
Before starting the robots, you may reverse the directions of some of them. All the grass on the lawn must be mowed.
Determine the minimum number of robots whose directions must be reversed so that all the grass on the lawn is eventually mowed. Otherwise, report that it is impossible to mow all the grass.
Input
The first line contains an integer $n$ ($2\le n\le 10^5$), the number of robots.
The next $n$ lines describe the robots in order of their positions 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<\ldots<x_n\le 10^9$, $1\le p_i\le 10^9$; $d_i=-1$ means movement to the left, in the direction of decreasing coordinates, and $d_i=1$ means movement to the right, in the direction of increasing coordinates). The beginning and end of the lawn are at $x_1=0$ and $x_n$, respectively.
Output
Print $-1$ on a single line if it is impossible to mow all the grass on the lawn. Otherwise, print one number: the number of robots whose directions must be reversed so that the lawn is mowed.
Subtasks
| Subtask | Points | Restriction on $n$ | Additional restrictions | Required subtasks |
|---|---|---|---|---|
| 1 | 23 | $n\le 10$ | Examples | |
| 2 | 16 | All robots initially face right ($d_i=1$) | ||
| 3 | 17 | $n\le 1000$ | Examples, 1 | |
| 4 | 13 | $x_i=i-1,\ p_i=1$ | ||
| 5 | 14 | $p_i=10^9$ | ||
| 6 | 17 | No additional restrictions | Examples, 1–5 |
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, reverse the robot standing in the middle.