题目描述

随着油价的暴跌，企鹅 Pengu 决定去拜访老鼠 Squeaky，距离他的家有 $D$ 公里。

Pengu 的车辆从出发时拥有 $F$ 升燃料，每公里消耗 $1$ 升燃料，并且车辆在任何时候都能容纳任意数量的燃料。

在 Pengu 和目的地之间有 $N$ 个加油站，第 $i$ 个加油站距离 Pengu 的家 $X_i$ 公里。
在每个加油站，Pengu 只能补充最多 $A_i$ 升燃料（为防止囤积便宜燃料），且只有当当前油量 $F \leq B_i$ 时才能加油（优先给燃料少的车辆）。注意，这里的 $F$ 是出发时的初始燃料量。

Pengu 希望能够以尽可能少的初始燃料 $F$ 完成这次旅行。

输入格式

• 第一行包含两个整数 $N$ 和 $D$，分别表示加油站的数量和目的地的距。
• 接下来 $N$ 行，每行包含三个整数 $X_i, A_i, B_i$，表示第 $i$ 个加油站的距离、加油量上限以及加油条件限制。

输出格式

输出一个整数，表示完成这次旅行所需的最小初始燃料 $F$。

1 10
4 8 6

4

5 100
50 30 25
50 40 25
25 25 25
75 20 25
5 5 25

20

提示

【样例解释】

对于样例 #1：

• 以 $F = 4$ 升燃料出发。
• 到达第一个加油站（$X_1 = 4$）时油量剩余 $4 - 4 = 0$ 升。
• 加油 $A_1 = 8$ 升，因为 $F \leq B_1 = 6$，此时油量为 $0 + 8 = 8$ 升。
• 到达目的地（$X = 10$）时油量剩余 $8 - (10 - 4) = 2$ 升。

这是可能的最小初始燃料量。

对于样例 #2：

• 以 $F = 20$ 升燃料出发。
• 到达第 $5$ 个加油站（$X_5 = 5$）时油量剩余 $20 - 5 = 15$ 升。
• 加油 $A_5 = 5$ 升，因为 $F \leq B_5 = 25$，此时油量为 $15 + 5 = 20$ 升。
• 到达第 $3$ 个加油站（$X_3 = 25$）时油量剩余 $20 - (25 - 5) = 0$ 升。
• 加油 $A_3 = 25$ 升，因为 $F \leq B_3 = 25$，此时油量为 $0 + 25 = 25$ 升。
• 到达第 $1$ 和第 $2$ 个加油站（$X_1 = X_2 = 50$）时油量剩余 $25 - (50 - 25) = 0$ 升。
• 分别加油 $A_1 + A_2 = 70$ 升，此时油量为 $0 + 70 = 70$ 升。
• 到达目的地（$X = 100$）时油量剩余 $70 - (100 - 50) = 20$ 升。

这是可能的最小初始燃料量。

【数据范围】

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_i, B_i, D \leq 10^9$
• $0 < X_i < D$