题目描述

译自 ROI 2024 Day2 T1. Восстание газонокосилок

在因诺波利斯市，草坪的修剪工作由电动机器人完成。可以将草坪看作是一条数线上的一段区域，机器人位于这条线的某些点上。机器人的体积可以忽略不计。草坪的最左端和最右端各有一个机器人，这两个位置之外没有草坪。每个机器人初始时面向左或面向右。

每个机器人的电量足以覆盖一定距离的草坪。夜间充电后，所有机器人会同时开始工作并以相同速度沿着直线移动。机器人将在以下三种情况下停止移动：

1. 当机器人的电量耗尽，即从起点移动了其能覆盖的最大距离。
2. 当机器人达到草坪的起始点或终点。
3. 当机器人与迎面而来或已经停在那里的另一机器人在同一点相遇。

在机器人启动前，你可以改变一些机器人的行进方向。你的任务是确定，为了完全修剪整个草坪，需要改变多少机器人的方向。如果不能完成整个草坪的修剪，输出 $-1$。

输入格式

第一行包含一个整数 $n\ (2 \leq n \leq 10^5)$，表示机器人的数量。

接下来 $n$ 行，每行描述一个机器人，包括三个整数 $x_i, p_i, d_i$，分别表示机器人的初始位置，它能覆盖的最大距离和它的初始朝向。其中 $d_i = -1$ 表示机器人向左（数值减小的方向），$d_i=1$ 表示机器人向右（数值增大的方向）。草坪的起始点和终点位于 $x_1=0$ 和 $x_n$。

输出格式

输出一个整数，表示需要改变方向的最小机器人数量以修剪整个草坪。如果无法完成任务，输出 $-1$。

3
0 1 -1
1 1 1
2 1 -1

1

在这个样例中，通过改变中间机器人的方向，可以覆盖整个草坪。

2
0 1 1
4 2 -1

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。