题目描述Description

一根长为 L 的独木桥上，有 N 只蚂蚁。给定每只蚂蚁的初始坐标 x_i、朝向（向左或向右）以及它背负的货物的重量 w_i。所有蚂蚁的爬行速度相同。

当两只蚂蚁相撞时，它们会立刻掉头（反向爬行）。当蚂蚁走到 x=0 或 x=L 时，就会掉下独木桥。

请问所有从左边（x=0）掉下独木桥的蚂蚁，它们背负的货物重量总和是多少？

输入格式Input

第一行包含两个整数 N 和 L，分别表示蚂蚁的数量和独木桥的长度。

接下来 N 行，每行包含三个整数 x_i、d_i、w_i：

• x_i：第 i 只蚂蚁的初始坐标

• d_i：第 i 只蚂蚁的朝向（0 表示向左，1 表示向右）

• w_i：第 i 只蚂蚁背负的货物重量

输出格式Output

输出一行一个整数，表示从左边掉下独木桥的蚂蚁背负的货物重量总和。

样例Sample

提示Hint

样例 1 说明

初始有 2 只蚂蚁向左（坐标 1 和 8），所以最终有 2 只蚂蚁从左边掉下。

按坐标排序后，最靠左的 2 只蚂蚁坐标为 1 和 5。

• 坐标 1 的蚂蚁重量为 5

• 坐标 5 的蚂蚁重量为 3

因此答案为 5 + 3 = 8。

数据范围

对于 100\% 的数据，保证：

• 1 \le N \le 10^5

• 2 \le L \le 10^9

• 1 \le x_i \le L-1

• 1 \le w_i \le 10^9

• 所有蚂蚁的初始坐标互不相同

出题Author

shepherdtoherd

来源Source

深圳技术大学第六届程序设计竞赛