该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$N$ 只蚂蚁以每秒 $1$ 厘米的速度在长为 $L$ 厘米的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反向爬回去。当掉落的蚂蚁重量大于等于总重量的一半时，整个过程结束。

对于每只蚂蚁，我们知道它的重量 $w[i]$ 、距离竿子左端的距离 $x[i]$，以及蚂蚁移动的方向 $d[i]$ （ $d[i]=1$ 表示向右， $d[i]=-1$ 表示向左）。 问在过程结束之前，蚂蚁们相遇的次数。

输入格式

第一行输入两个正整数 $N$ 和 $L$，分别表示蚂蚁数量，竿子长度；

之后 $N$ 行，每行三个整数 $w[i],x[i],d[i]$，描述一只蚂蚁。

其中 $N\le 50000,L\le 10^9,w[i]\le 1000,0<x[i]<L$ 且所有 $x[i]$ 均不同。

输出格式

输出一行，包含答案。

样例输入输出

3 5
1 1 1
2 2 -1
3 3 -1

2

说明/提示

对于8%的数据，$1\le N \le 5$ ；

另有23%的数据， $w[i]=1$；

对于54%的数据， $1\le N\le 100$；

对于100%的数据，$1\le N \le 50000,2\le L \le 10^9,1\le w[i] \le 1000,d[i]\in \{ 1,-1 \}$ ，保证$0 < x[i] <L$ 且所有$x[i]$ 均不相同。

在这个例子中，蚂蚁按如下方式移动：

1. 第一和第二只蚂蚁于时刻 0.5在位置 1.5相遇。此时第一只蚂蚁速度为 − 1，第二只蚂蚁速度为1 。
2. 第二和第三只蚂蚁于时刻1 在位置2 相遇。此时第二只蚂蚁速度为 −1 ，第三只蚂蚁速度为1 。
3. 第一只蚂蚁于时刻 2到达左边后掉落。
4. 第二只蚂蚁于时刻3 到达左边后掉落。
5. 由于掉落的蚂蚁的总重量已经是所有蚂蚁的总重量的一半及以上，这个过程此时终止。如果继续进行下 去，第三只蚂蚁将会在时刻 4从右边掉落。中间发生了恰好两次相遇。

题目来源

2023年城阳区程序设计竞赛初中组 T4 Ant