因诺波利斯的草坪由电动割草机器人修剪。我们可以认为草坪是一条数轴上的线段，一些机器人位于线段上的特定点。机器人的尺寸可以忽略不计。其中一个机器人位于草坪的起点（其左侧没有草坪），另一个位于终点（其右侧没有草坪）。每个机器人最初朝向两个方向之一：向右或向左。
第 $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 < \dots < 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