题目描述

有两个牛棚位于一维数轴上的点 0和 L处。

同时有$N$头奶牛位于数轴上不同的位置（将牛棚和奶牛看作点）。

每头奶牛$i$初始时位于某个位置$x_i$，并朝着正向或负向以一个单位每秒的速度移动，用一个等于$1$或$−1$的整数$d_i$表示。

每头奶牛还拥有一个在范围$ [1,10^3] $内的重量。

所有奶牛始终以恒定的速度移动，直到以下事件之一发生：

如果奶牛$i$移动到了一个牛棚，则奶牛 $i$停止移动。

当奶牛$i$和$j$占据了相同的点的时候，如果这一点不是一个牛棚，则发生了相遇。此时，奶牛$i$被赋予奶牛$j$先前的速度，反之亦然。注意奶牛可能在一个非整数点相遇。令$T$等于停止移动的奶牛（由于到达两个牛棚之一而停止移动）的重量之和至少等于所有奶牛的重量之和的一半的最早时刻。

请求出在时刻$0…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≤L≤10^9,$

$1≤N≤5×10^4$

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

第一和第二头奶牛于时刻 0.5在位置 1.5相遇。此时第一头奶牛拥有速度 −1，第二头奶牛拥有速度 1。

第二和第三头奶牛于时刻 1在位置 2相遇。此时第二头奶牛拥有速度 −1，第三头奶牛拥有速度 1。

第一头奶牛于时刻 2到达左边的牛棚。

第二头奶牛于时刻 3到达左边的牛棚。

由于到达牛棚的奶牛的总重量已经至少是所有奶牛的总重量的一半，这个过程此时终止。如果继续进行下去，第三头奶牛将会在时刻 4到达右边的牛棚。

发生了恰好两次相遇。