CF141D.Take-off Ramps

Vasya participates in a ski race along the X axis. The start is at point 0, and the finish is at L, that is, at a distance L meters from the start in the positive direction of the axis. Vasya has been training so hard that he can run one meter in exactly one second.

Besides, there are n take-off ramps on the track, each ramp is characterized by four numbers:

• x__i represents the ramp's coordinate
• d__i represents from how many meters Vasya will land if he goes down this ramp
• t__i represents the flight time in seconds
• p__i is the number, indicating for how many meters Vasya should gather speed to get ready and fly off the ramp. As Vasya gathers speed, he should ski on the snow (that is, he should not be flying), but his speed still equals one meter per second.

Vasya is allowed to move in any direction on the X axis, but he is prohibited to cross the start line, that is go to the negative semiaxis. Vasya himself chooses which take-off ramps he will use and in what order, that is, he is not obliged to take off from all the ramps he encounters. Specifically, Vasya can skip the ramp. It is guaranteed that x__i + d__i ≤ L, that is, Vasya cannot cross the finish line in flight.

Vasya can jump from the ramp only in the positive direction of X axis. More formally, when using the i-th ramp, Vasya starts gathering speed at point x__i - p__i, jumps at point x__i, and lands at point x__i + d__i. He cannot use the ramp in opposite direction.

Your task is to find the minimum time that Vasya will spend to cover the distance.

瓦西娅参加一场沿 $X$ 轴进行的滑雪比赛。起点位于坐标 $0$，终点位于坐标 $L$，即在 $X$ 轴正方向距离起点 $L$ 米处。瓦西娅经过刻苦训练，能够以恰好每秒 $1$ 米的速度滑行。

此外，赛道上共有 $n$ 个起跳坡道（ramp），每个坡道由四个参数刻画：

• $x_i$ 表示该坡道所在位置的坐标；
• $d_i$ 表示瓦西娅沿该坡道滑下后将飞行并着陆的距离（即从起跳点向前飞行 $d_i$ 米）；
• $t_i$ 表示此次飞行所用的时间（单位：秒）；
• $p_i$ 表示瓦西娅为准备起跳而需提前加速滑行的距离（单位：米）。在加速阶段，他必须在雪面上滑行（即不可处于飞行状态），但其滑行速度仍为每秒 $1$ 米。

瓦西娅可以在 $X$ 轴上朝任意方向移动，但禁止越过起点线，即不能进入负半轴（$x < 0$）。瓦西娅可自主决定使用哪些起跳坡道以及使用的顺序；他无需使用所有途经的坡道，亦可选择跳过任意坡道。特别地，瓦西娅可以完全忽略某个坡道。题目保证对每个坡道均有 $x_i + d_i \leq L$，即瓦西娅不可能在飞行过程中越过终点线。

瓦西娅仅允许沿 $X$ 轴正方向从坡道起跳。更准确地说：当使用第 $i$ 个坡道时，瓦西娅须从位置 $x_i - p_i$ 开始加速滑行，在位置 $x_i$ 处起跳，并最终在位置 $x_i + d_i$ 处着陆；他不允许反向（即朝负方向）使用该坡道。

你的任务是求出瓦西娅完成全程所需的最短时间。

The first line contains two integers n and L (0 ≤ n ≤ 105, 1 ≤ L ≤ 109). Then n lines contain the descriptions of the ramps, each description is on a single line. Each description is a group of four non-negative integers x__i, d__i, t__i, p__i (0 ≤ x__i ≤ L, 1 ≤ d__i, t__i, p__i ≤ 109, x__i + d__i ≤ L).

第一行包含两个整数 $n$ 和 $L$（$0 ≤ n ≤ 10^5$，$1 ≤ L ≤ 10^9$）。接下来 $n$ 行描述斜坡，每行一个斜坡的描述。每个描述由四个非负整数 $x_i$、$d_i$、$t_i$、$p_i$ 组成（$0 ≤ x_i ≤ L$，$1 ≤ d_i,\,t_i,\,p_i ≤ 10^9$，且 $x_i + d_i ≤ L$）。

Print in the first line the minimum time in seconds Vasya needs to complete the track. Print in the second line k — the number of take-off ramps that Vasya needs to use, and print on the third line of output k numbers the number the take-off ramps Vasya used in the order in which he used them. Print each number exactly once, separate the numbers with a space. The ramps are numbered starting from 1 in the order in which they are given in the input.

第一行输出瓦夏完成赛道所需的最短时间（单位：秒）。
第二行输出 $k$ —— 瓦夏需要使用的起飞斜坡的数量；第三行输出 $k$ 个数字，表示瓦夏按使用顺序所使用的起飞斜坡的编号。每个编号仅输出一次，数字之间用空格分隔。斜坡编号从 1 开始，按输入中给出的顺序依次编号。

In the first sample, Vasya cannot use ramp 2, because then he will need to gather speed starting from point -3, which is not permitted by the statement. The optimal option is using ramp 1, the resulting time is: moving to the point of gathering speed + gathering speed until reaching the takeoff ramp + flight time + moving to the finish line = 0 + 5 + 5 + 5 = 15.

In the second sample using ramp 1 is not optimal for Vasya as _t_1 > _d_1. The optimal option is using ramp 2, the resulting time is: moving to the point of gathering speed + gathering speed until reaching the takeoff ramp + flight time + moving to the finish line = 14 + 1 + 1 + 0 = 16.

在第一个样例中，Vasya 无法使用斜坡 2，因为这将导致他需要从位置 $-3$ 开始加速，而题目说明中不允许这样做。最优方案是使用斜坡 1，总耗时为：移动至加速起始点所需时间 + 加速至起飞斜坡所需时间 + 飞行时间 + 移动至终点线所需时间 $= 0 + 5 + 5 + 5 = 15$。

在第二个样例中，对 Vasya 而言使用斜坡 1 并非最优，因为 $t_1 > d_1$。最优方案是使用斜坡 2，总耗时为：移动至加速起始点所需时间 + 加速至起飞斜坡所需时间 + 飞行时间 + 移动至终点线所需时间 $= 14 + 1 + 1 + 0 = 16$。