走地鸡学飞
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

SCUTkk 认为走地鸡们地面上走来走去已经太久了,现在它想要学飞!

于是 SCUTkk 报名参加了 SCUT 飞行训练营。训练营有一张训练地图,形如**一条数轴**,数轴上的每个**非零**整数点都可能是**空地或者有一个任务**,每个任务包含一个**飞行高度要求 h** 和一个 **任务奖励 v**,**且只能被完成一次**。

保证任意一个位置上**至多只有一个**任务,**零点上没有任务**。

每当 SCUTkk 到达一个有**未被完成**的任务的位置,且他的飞行能力**大于等于**该位置任务的飞行高度要求 h 时,它就可以完成该位置的任务,并使自己的**飞行能力永久增加**任务奖励 v

训练开始时,SCUTkk会出现在**零点处**,初始时它**飞行能力是 x** 。在训练中,SCUTkk只能在**空地或者已经完成过的**任务位置上**一格格左右移动**。如果要移动到一个**有任务且未完成过**的位置上,SCUTkk **必须先完成**这个位置上的任务。当场上不存在 SCUTkk 能**到达并完成**的任务时,训练结束。

SCUTkk 想在训练中尽可能的提升自己的飞行高度,但它算不清楚这么复杂的问题。于是它想请你帮它进行计算一下,经过训练之后它的**飞行能力最大能达到多少**?

输入描述:

第一行两个整数:地图上的任务总数 n (1 \leq n \leq 2 \times 10^{5}) ,初始飞行能力 x (1 \leq x \leq 10^{9}) 。

接下来 n 行,每行三个整数表示一个任务:任务位置 a (-10^{9} \leq a_i \leq 10^{9}, a_i \neq 0) ,飞行高度要求 h (1 \leq h_i \leq 10^{9}) , 任务奖励 v (0 \leq v_i \leq 2 \times 10^{3}) 。

对任意的 1 \leq i, j \leq n (i \neq j) ,保证 a_i \neq a_j

输出描述:

一行一个整数,表示经过训练之后 SCUTkk **飞行能力可能达到的最大值**。
示例1

输入

复制
5 1
-1 1 2
7 10 15
-3 5 1
1 3 3
10 5 3

输出

复制
7

说明

初始时飞行能力为 1 , SCUTkk 可以先到 -1 处完成任务,使飞行能力增加到 3 。

然后 SCUTkk 可以到 1 处完成任务,使飞行能力增加到 3 。

然后 SCUTkk 可以到 -3 处完成任务,使飞行能力增加到 7 。

接下来 SCUTkk 发现 7 处的任务无法完成,而由于 7 处的任务未完成,10 处的任务可以完成但无法越过 7 处到达,因此场上不再有能被完成的任务了,最大飞行能力就是 7。