Иннополис の芝生は、電動の芝刈りロボットによって刈られています。芝生は数直線上の線分であり、そのいくつかの点に芝刈りロボットが置かれているものとします。ロボットの大きさは無視できます。1 台のロボットが芝生の始点にあり、その左側には芝生がありません。また、1 台が終点にあり、その右側には芝生がありません。各ロボットは最初、右または左のいずれかを向いています。
$i$ 番目のロボットの充電量は、芝生を $p_i$ メートル刈るのに十分です。夜間の充電後、すべてのロボットが同時に作業を始め、同じ速さで動きます。各ロボットは、自分が向いている方向に直線上を進みます。ロボットは次の 3 つの場合のいずれかで停止します。
- 充電がなくなった場合。つまり、$i$ 番目のロボットが出発点から $p_i$ メートル進んだ場合です。
- 芝生の始点または終点に到達した場合。
- 向かい合う方向に動いていた別のロボット、またはその点ですでに停止していた別のロボットと、同じ点で出会った場合。
ロボットを起動する前に、いくつかのロボットの向きを反対に変えることができます。芝生全体の草を刈る必要があります。
最終的に芝生全体の草を刈るために、向きを変える必要があるロボットの台数の最小値を求めてください。芝生全体の草を刈ることが不可能なら、そのことを報告してください。
入力
最初の行には整数 $n$（$2\le n\le10^5$）が含まれます。これはロボットの台数です。
続く $n$ 行には、直線上で左から右に並ぶ順にロボットの情報が与えられます。各ロボットは 3 つの整数 $x_i,p_i,d_i$ で表されます。これらは、初期位置、進むことのできる距離（メートル）、進行方向です（$0=x_1<x_2<\cdots<x_n\le10^9$、$1\le p_i\le10^9$。$d_i=-1$ は座標が減少する方向、つまり左への移動を表し、$d_i=1$ は座標が増加する方向、つまり右への移動を表します）。芝生の始点と終点は、それぞれ $x_1=0$ と $x_n$ にあります。
出力
芝生全体の草を刈ることが不可能なら、1 行に $-1$ を出力してください。そうでなければ、芝生全体を刈るために向きを反対に変える必要があるロボットの台数を、1 つの数として出力してください。
小課題
| 小課題 | 配点 | $n$ の制約 | 追加の制約 | 必須の小課題 |
|---|---|---|---|---|
| $1$ | $23$ | $n\le10$ | 入出力例 | |
| $2$ | $16$ | 最初はすべてのロボットが右を向いている（$d_i=1$） | ||
| $3$ | $17$ | $n\le1000$ | 入出力例, $1$ | |
| $4$ | $13$ | $x_i=i-1$, $p_i=1$ | ||
| $5$ | $14$ | $p_i=10^9$ | ||
| $6$ | $17$ | 追加の制約なし | 入出力例, $1$–$5$ |
入出力例
入力 1
3 0 1 -1 1 1 1 2 1 -1
出力 1
1
入力 2
2 0 1 1 4 2 -1
出力 2
-1
注記
最初の例は図に示されています。芝生全体の草を刈るには、例えば中央にあるロボットの向きを反対に変えることができます。