CF141D Take-off Ramps

Vasya 参加了一场沿 $ X $ 轴进行的滑雪比赛。起点在 $ 0 $ 点，终点在 $ L $ 点，也就是说，终点在起点正方向距离 $ L $ 米的位置。Vasya 经过刻苦训练，可以精确地用一秒钟滑行一米。 此外，赛道上有 $ n $ 个跳板，每个跳板由四个数字描述： - $ x_{i} $ 表示跳板的位置坐标； - $ d_{i} $ 表示如果 Vasya 使用该跳板，他将从多远的地方着陆； - $ t_{i} $ 表示飞行所需的秒数； - $ p_{i} $ 表示 Vasya 需要预热（助跑）多远的距离以准备飞跃该跳板。在预热的过程中，Vasya 需要在雪地上滑行（即未处于飞行状态），但滑行速度仍保持一米每秒。 Vasya 可以在 $ X $ 轴的任意方向移动，但不得越过起点线（即不得进入负半轴）。Vasya 可自由选择使用哪些跳板以及使用顺序，也可以跳过某些跳板。保证 $ x_{i}+d_{i} \leq L $ ，即 Vasya 不可能在飞行中越过终点线。 Vasya 仅能向 $ X $ 轴的正方向使用跳板。更具体地，当使用第 $ i $ 个跳板时，Vasya 从 $ x_{i}-p_{i} $ 处开始助跑，在 $ x_{i} $ 处起跳，并在 $ x_{i}+d_{i} $ 处着陆。他不能反方向使用跳板。 你的任务是求出 Vasya 完成全程所需的最少时间。

第一行包含两个整数 $ n $ 和 $ L $（$ 0 \leq n \leq 10^{5} $，$ 1 \leq L \leq 10^{9} $）。接下来的 $ n $ 行，每行含四个非负整数 $ x_{i} $、$ d_{i} $、$ t_{i} $、$ p_{i} $（$ 0 \leq x_{i} \leq L $，$ 1 \leq d_{i}, t_{i}, p_{i} \leq 10^{9} $，$ x_{i}+d_{i} \leq L $），描述一个跳板。

第一行输出 Vasya 完成比赛的最短时间（单位：秒）。 第二行输出 $ k $ —— Vasya 需要用到的跳板数量。 第三行输出 $ k $ 个整数，顺序为 Vasya 实际用到的跳板编号，编号按输入顺序从 1 开始，每个编号只出现一次，编号之间用空格隔开。

对于第一组样例，Vasya 不能用第 2 个跳板，因为那样他需要从 $ -3 $ 点开始助跑，这是不允许的。最优方案是使用第 1 个跳板，总共用时为：移动到助跑起点 + 助跑到跳板 + 飞行时间 + 移动到终点 $ =0+5+5+5=15 $。 对于第二组样例，直接用第 1 个跳板不是最优的，因为 $ t_{1}>d_{1} $。最优方案是使用第 2 个跳板，用时为：移动到助跑起点 + 助跑到跳板 + 飞行时间 + 移动到终点 $ =14+1+1+0=16 $。 由 ChatGPT 5 翻译