Vasya 参加沿 X 轴的滑雪比赛。起点位于点 0,终点位于 L,即沿轴正方向距起点 L 米处。瓦西亚一直在刻苦训练,他可以在一秒钟内跑完一米。
此外,赛道上有n个起飞坡道,每个坡道由四个数字表示:
- xi 代表斜坡的坐标
- di 表示如果 Vasya 走下这个坡道,他将从多少米处着陆
- ti 表示飞行时间(以秒为单位)
- pi 是数字,表示 Vasya 应加速多少米以做好准备并飞离坡道。当瓦夏(Vasya)加速时,他应该在雪上滑雪(也就是说,他不应该飞行),但他的速度仍然等于每秒一米。
Vasya 可以在 X 轴上任意方向移动,但禁止越过起始线,即向负半轴移动。瓦夏自己选择他将使用哪些起飞坡道以及以什么顺序,也就是说,他没有义务从他遇到的所有坡道起飞。具体来说,瓦西亚可以跳过坡道。保证xi + di ≤ L,即Vasya在飞行中无法冲过终点线。
Vasya 只能在 X 轴正方向上从斜坡跳跃。更正式地说,当使用第 i 个坡道时,Vasya 开始在 xi - pi 点加速,在 xi 点跳跃,并在 xi + di 点着陆。他不能使用相反方向的坡道。
你的任务是找出 Vasya 走完这段距离所需的最短时间。
输入
第一行包含两个整数 n 和 L (0 ≤ n ≤ 105, 1 ≤ L ≤ 109)。然后 n 行包含斜坡的描述,每个描述都在一行上。每个描述都是一组四个非负整数 xi, di, ti, pi (0 ≤ xi ≤ L, 1 ≤ di, ti, pi ≤ 109, xi + di ≤ L)。
输出
在第一行打印 Vasya 完成赛道所需的最短时间(以秒为单位)。在第二行中打印 k — Vasya 需要使用的起飞坡道的数量,并在输出 k 的第三行中打印 Vasya 按照使用顺序使用的起飞坡道的数量。每个数字只打印一次,用空格分隔数字。斜坡按照输入中给出的顺序从 1 开始编号。
示例
输入 #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
注意
在第一个示例中,Vasya 无法使用斜坡 2,因为那样他将需要从点 -3 开始收集速度,这是语句不允许的。最佳选择是使用坡道 1,得到的时间为:移动到聚集点速度 + 到达起飞坡道聚集速度 + 飞行时间 + 移动到终点线 = 0 + 5 + 5 + 5 = 15。
在第二个示例中,使用斜坡 1 对于 Vasya 来说并不是最佳的,因为 t1 > d1。最佳选择是使用坡道 2,得到的时间为:移动到聚集点速度 + 到达起飞坡道时聚集速度 + 飞行时间 + 移动到终点线 = 14 + 1 + 1 + 0 = 16。