You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 ROI 2024 D2T1。

草坪需要由电动割草机器人割草。我们认为草坪是一个数轴上的线段，其中在某些点上有割草机器人。机器人的大小可以忽略不计。一个机器人位于草坪的起点（起点左侧没有草坪），另一个机器人位于终点（终点右侧没有草坪）。每个机器人最初朝一个方向行驶：要么向右，要么向左。

第 $i$ 个机器人的电量足够处理 $p_i$ 米的草坪。所有机器人在夜间充电后同时启动，并以相同的速度移动。每个机器人沿直线朝其方向移动。机器人在以下三种情况下停止：

1. 如果机器人的电量耗尽。换句话说，若第 $i$ 个机器人从起点行驶了 $p_i$ 米。
2. 如果机器人到达了草坪的起始点或终点。
3. 如果机器人在某处遇到了另一个朝相反方向行驶或停在此处的机器人。

题目描述

在启动机器人之前，可以将某些机器人的方向更改为相反方向。为了割光整个草坪，你需要确定最少需要改变方向的机器人数量，使得最终整个草坪都能被割光。如果无论如何都无法使得整个草坪被割完，输出 -1。

输入格式

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

接下来的 $n$ 行，每行描述一个机器人，按从左到右的顺序给出。每个机器人由三个整数 $x_i$, $p_i$, $d_i$ 描述，它们分别是机器人的初始位置、它可以行驶的距离以及行驶方向（$0 = x_1 < x_2 < \cdots < x_n \leq 10^9$，$1 \leq p_i \leq 10^9$，$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

提示

样例 $1$ 与题目背景中图片的情形一致，可以通过改变中间机器人的方向来使得所有草坪都被割完。

对于 $100\%$ 的数据，范围见输入格式。