You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

一列火车从起点出发，初始高度为 $0$，以速度 $1$ 匀速向右行驶（即每秒前进 $1$ 单位水平距离）。火车的出发时间为给定的常数 $D$（即在时间 $D$ 时从起点出发）。从时间 $0$ 开始就可以建造轨道。

共有 $n$ 段轨道需要建造，编号 $1$ 到 $n$。每段轨道 $i$ 由三个整数参数描述：

• 长度 $L_i$：正整数，表示该段轨道的水平距离。
• 高度变化 $S_i$：整数，表示火车行驶完该段轨道后的高度变化量。若 $S_i > 0$ 则为上坡（高度增加 $S_i$），若 $S_i < 0$ 则为下坡（高度减少 $|S_i|$）。
• 建造时间 $T_i$：正整数，表示建造该段轨道所需的时间。

你需要决定这些轨道的 行驶顺序（即火车经过它们的先后次序）以及 建造顺序（即建造它们的先后次序）。

约束条件

1. 建造顺序约束：同一时间只能建造一段轨道，且建造过程中不能中断。对于行驶顺序中的第 $k$ 段轨道，它必须在火车到达该段起点之前建造完成，即其建造完成时间 $\le$ 火车到达该段起点的时间。
2. 高度非负：火车在行驶过程中的任意时刻，高度不能低于 $0$。
3. 终点高度为零：在行驶完所有 $n$ 段轨道之后，火车的高度必须恰好为 $0$。

目标

在所有满足上述条件的行驶顺序和建造方案中，最小化火车行驶过程中的最大高度。如果不存在任何满足条件的方案，输出 $-1$。

输入格式

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

接下来 $n$ 行，每行三个整数 $L_i, S_i, T_i$。

输出格式

一个整数，表示最小可能的最大高度；若无解则输出 $-1$。

样例

样例输入 1

2 5
2 1 3
1 -1 2

样例输出 1

1

解释：可在出发前完成两段轨道的建造（建造总时间 $3+2=5$）。行驶时先上坡后下坡，最大高度为 $1$。

样例输入 2

7 20
3 2 3
4 3 4
2 -1 2
3 -2 3
2 1 2
1 -2 1
2 -1 2

样例输出 2

3

解释：按行驶顺序 $2,4,1,3,5,7,6$（即轨道2、轨道4、轨道1、轨道3、轨道5、轨道7、轨道6）行驶，整个过程高度不超过 $3$，且该值是最优的。

样例输入 3

7 20
3 2 3
4 3 4
2 -1 2
3 -2 3
2 1 2
1 2 1
2 -1 2

样例输出 3

-1

解释：无法使终点高度为零，因此无解。

数据范围

• $1 \leq n \leq 20$
• $1 \leq D \leq 10^{10}$
• $1 \leq L_i, T_i \leq 10^{10}$
• $|S_i| \leq 10^{10}$