徐老师的玩具小车

题目描述

在一条长度为 $len$ 的线段上，依次摆放着 $n$ 辆小车。第 $i$ 辆小车的喜爱度为 $a_i$，初始位置为 $x_i$，行进方向为 $dir_i$（$1$ 向右，$-1$ 向左）。所有小车均可视为质点，速度恒为每秒 $1$ 厘米。

两车相遇时会发生碰撞，双方都立即反向，速度大小不变。小车到达线段端点 $0$ 或 $len$ 后立即掉落，不再运动。

设全部小车的喜爱度之和为 $W$。在梦境中，从开始运动到已经掉落的小车的喜爱度之和首次满足 $2\times\text{掉落喜爱度}\ge W$ 的时刻，统计一共发生了多少次碰撞。

如果达到上述阈值的时刻恰好有碰撞，也应计入该时刻的碰撞。

输入格式

第一行两个整数 $n,len$。

接下来的 $n$ 行，每行三个整数 $a_i,x_i,dir_i$，小车按初始位置从左到右排列。

输出格式

输出一个整数，表示从开始到梦醒时（含梦醒时刻）发生的碰撞次数。

数据范围

$1\le n\le10^5$，$2\le len\le10^9$，$1\le a_i\le10^3$，$dir_i\in\{-1,1\}$，$0<x_i<len$，所有 $x_i$ 互不相同。

样例 1

5 15
3 1 1
3 2 -1
3 3 -1
1 6 1
1 12 -1

3

样例 2

5 15
627 5 1
238 7 -1
753 9 -1
740 10 -1
612 13 1

3