P11320 [NOISG 2020 Qualification] Fuel Station

随着油价的暴跌，企鹅 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： - 以 $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$ | 子任务编号 | 分值 | 限制条件 | |:--------:|:---------:|:--------------------------:| | $1$ | $7$ | $N = 1$ | | $2$ | $13$ | $B_i = 10^9$ | | $3$ | $17$ | $1 \leq D \leq 10^4, 1 \leq N \leq 10^4$ | | $4$ | $12$ | $1 \leq D \leq 10^4$ | | $5$ | $19$ | $1 \leq N \leq 16$ | | $6$ | $11$ | $1 \leq N \leq 10^4$ | | $7$ | $21$ | 无其他限制 |