Иннополис 的草坪由電動割草機器人修剪。我們把草坪視為數線上的一條線段，在其中的某些點放置割草機器人。可以忽略機器人的大小。一個機器人位於草坪的起點（它左側沒有草坪），另一個位於草坪的終點（它右側沒有草坪）。每個機器人最初朝向兩個方向之一：向右或向左。
第 $i$ 個機器人的電量足夠修剪 $p_i$ 公尺的草坪。經過一夜充電後，所有機器人同時開始工作，並以相同的速度移動。每個機器人沿直線向其朝向的方向移動。機器人在下列三種情況之一發生時停止：
- 機器人的電量耗盡。換句話說，第 $i$ 個機器人從起點移動了 $p_i$ 公尺。
- 機器人到達草坪的起點或終點。
- 機器人在某一點遇到另一個機器人，而那個機器人是迎面移動而來，或先前已經停在該點。
啟動機器人之前，你可以將某些機器人的朝向改為相反方向。需要將整片草坪的草全部割完。
求至少要改變多少個機器人的朝向，才能使整片草坪最終全部被修剪。如果無法割完所有的草，則報告不可能。
輸入格式
第一行包含一個整數 $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$。否則，輸出一個數，表示為了割完整片草坪，必須將朝向改為相反方向的機器人數量。
子任務
| 子任務 | 分值 | $n$ 的限制 | 額外限制 | 所需子任務 |
|---|---|---|---|---|
| $1$ | $23$ | $n\le 10$ | 範例 | |
| $2$ | $16$ | 最初所有機器人都朝向右方（$d_i=1$） | ||
| $3$ | $17$ | $n\le 1000$ | 範例、$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
說明
第一個範例如圖所示。為了割完所有的草，例如可以將位於中間的機器人掉頭。