题目描述

有两个牛棚位于一维数轴上的点 $0$ 和 $L$ 处（$1 \leq L \leq 10^9$）。同时有 $N$ 头奶牛（$1 \leq N \leq 5 \times 10^4$）位于数轴上不同的位置（将牛棚和奶牛看作点）。每头奶牛 $i$ 初始时位于某个位置 $x_i$，并朝着正向或负向以一个单位每秒的速度移动，用一个等于 $1$ 或 $-1$ 的整数 $d_i$ 表示。每头奶牛还拥有一个在范围 $[1,10^3]$ 内的重量。所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

• 如果奶牛 $i$ 移动到了一个牛棚，则奶牛 $i$ 停止移动。
• 当奶牛 $i$ 和 $j$ 占据了相同的点的时候，并且这一点不是一个牛棚，则发生了相遇。此时，奶牛 $i$ 被赋予奶牛 $j$ 先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。

令 $T$ 等于停止移动的奶牛（由于到达两个牛棚之一）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。请求出在时刻 $0 \ldots T$（包括时刻 $T$）之间发生的奶牛对相遇的总数。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $L$。

以下 $N$ 行，每行包含三个空格分隔的整数 $w_i$，$x_i$ 以及 $d_i$。所有的位置 $x_i$ 各不相同，并且满足 $0<x_i<L$。

输出格式

输出一行，包含答案。

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

2

提示

样例解释

在这个例子中，奶牛们按如下方式移动：

1. 第一和第二头奶牛于时刻 0.5 在位置 1.5 相遇。此时第一头奶牛拥有速度 -1，第二头奶牛拥有速度 1。
2. 第二和第三头奶牛于时刻 1 在位置 2 相遇。此时第二头奶牛拥有速度 −1，第三头奶牛拥有速度 1。
3. 第一头奶牛于时刻 2 到达左边的牛棚。
4. 第二头奶牛于时刻 3 到达左边的牛棚。
5. 由于到达牛棚的奶牛的总重量已经至少是所有奶牛的总重量的一半，这个过程此时终止。如果继续进行下去，第三头奶牛将会在时刻 4 到达右边的牛棚。

发生了恰好两次相遇。

子任务

测试点 $2\sim 4$ 满足 $N\le 10^2$，并且对所有 $i$，$w_i=1$。

测试点 $5\sim 7$ 满足 $N\le 10^2$。

供题：Benjamin Qi