题目描述

有两个牛棚位于一维数轴上的点0和L处$(1≤L≤10^9$)。同时有N头奶牛$(1≤N≤5*10^4)$位于数轴上不同的位置（将牛棚和奶牛看作点)。
每头奶牛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. 第⼀和第⼆头奶⽜于时刻 0.5 在位置 1.5 相遇。此时第⼀头奶⽜拥有速度-1，第⼆头奶⽜拥有速度 。

2. 第⼆和第三头奶⽜于时刻 1 在位置 2 相遇。此时第⼆头奶⽜拥有速度-1，第三头奶⽜拥有速度 。

3. 第⼀头奶⽜于时刻 2 到达左边的⽜棚。

4. 第⼆头奶⽜于时刻 3 到达左边的⽜棚。

5. 由于到达⽜棚的奶⽜的总重量已经⾄少是所有奶⽜的总重量的⼀半，这个过程此时终⽌。如果继续进⾏下去， 第三头奶⽜将会在时刻 4 到达右边的⽜棚。

   发⽣了恰好两次相遇。

注释

测试点2-4满足N≤100，并且对所有的i，$w_i$ = 1。 测试点5-7满足N≤100。