题目描述

Vasya 参加了一场沿 $X$ 轴进行的滑雪比赛。起点在 0 号点，终点在 $L$ 号点，即沿轴正方向离起点 $L$ 米。Vasya 练得非常狠，他在雪地上每秒恰好滑行 1 米。

此外，赛道上有 $n$ 条起跳坡道，每条坡道用四个数描述：

• $x_i$ 表示坡道的坐标；
• $d_i$ 表示 Vasya 从这个坡道飞下后落地的距离（米）；
• $t_i$ 表示飞行时间（秒）；
• $p_i$ 表示 Vasya 需要助跑多少米才能起跳。助跑时他必须滑在雪上（即不在飞行状态），但速度仍是每秒 1 米。

Vasya 可以在 $X$ 轴上沿任意方向移动，但禁止越过起跑线，即不能进入负半轴。Vasya 自己决定使用哪些坡道和使用顺序——他没必要把遇到的每个坡道都用上，可以跳过某个坡道。保证 $x_i + d_i \le L$，即飞行中 Vasya 不会越过终点线。

Vasya 只能从坡道上沿 $X$ 轴正方向起跳。 严格地说，使用第 $i$ 条坡道时，Vasya 从点 $x_i - p_i$ 开始助跑，在点 $x_i$ 起跳，于点 $x_i + d_i$ 落地。他不能反方向使用坡道。

求 Vasya 滑完全程所需的最短时间。

输入格式

第一行包含两个整数 $n$ 和 $L$（$0 \le n \le 10^5$，$1 \le L \le 10^9$）。接下来 $n$ 行每行一条坡道描述：四个非负整数 $x_i$、$d_i$、$t_i$、$p_i$（$0 \le x_i \le L$，$1 \le d_i, t_i, p_i \le 10^9$，$x_i + d_i \le L$）。

输出格式

第一行输出 Vasya 完成赛道所需的最短秒数。第二行输出 $k$——Vasya 需要使用的坡道数。第三行输出他按使用顺序所用的坡道编号，每个数恰好输出一次，用空格隔开。坡道按输入顺序从 1 开始编号。

2 20
5 10 5 5
4 16 1 7

15
1
1

2 20
9 8 12 6
15 5 1 1

16
1
2

说明/提示

第一组样例中，Vasya 不能使用坡道 2，因为那样助跑点将是 $-3$，题面不允许。最优方案是用坡道 1，总时间为：移动到助跑起点 + 助跑到起跳点 + 飞行时间 + 从落点到终点 = 0 + 5 + 5 + 5 = 15。

第二组样例中，用坡道 1 不优（$t_1 \gt d_1$）。最优方案是用坡道 2，总时间为助跑 + 飞行 + 移动。