Иннополис 的草坪由电动割草机器人修剪。我们认为草坪是数轴上的一条线段，割草机器人位于这条线段上的某些点。机器人的大小可以忽略不计。一个机器人位于草坪的起点（其左侧没有草坪），另一个机器人位于草坪的终点（其右侧没有草坪）。每个机器人最初朝向两个方向之一：向右或向左。
第 $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
说明
第一个样例如图所示。为了修剪所有草，例如可以将位于中间的机器人的朝向反转。