Take-off Ramps

题意翻译

Gnar 从数轴的 0 m 处出发，打算向右走到数轴的 $L$ m 处，Gnar 行走的速度是 1 m/s，Gnar 可以向左或者向右走，但不能走到 0 m 处的左侧。同时在数轴上有 $n$ 个点，每个点允许 Gnar 在这里起跳一次，且每个点有四个参数： - $x_i$ 代表第 $i$ 个点在数轴的 $x_i$ m 处 - $d_i$ 代表 Gnar 从这个点能够向右跳多远 - $t_i$ 代表 Gnar 跳过这段路的时间 - $p_i$ 代表 Gnar 需要在这个点之前**向右行走**至少 $p_i$ 的距离才能够起跳 求 Gnar 最短需要多少时间，以及在哪些点起跳。

题目描述

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.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ L $ ( $ 0<=n<=10^{5} $ , $ 1<=L<=10^{9} $ ). 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}<=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.

输入输出样例

输入样例 #1

2 20
5 10 5 5
4 16 1 7

输出样例 #1

15
1
1 

输入样例 #2

2 20
9 8 12 6
15 5 1 1

输出样例 #2

16
1
2 

说明

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}&gt;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 $ .