D. Трамплины
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вася участвует в лыжной гонке по оси X. Старт находится в точке 0, а финиш — в точке L, то есть на расстоянии L метров от старта в положительном направлении оси. Вася так сильно натренирован, что может пробежать один метр ровно за одну секунду.

Кроме того, на трассе расположено n трамплинов, каждый трамплин характеризуется четырьмя числами:

  • xi — координата трамплина,
  • di — через сколько метров приземлится Вася, если наедет на этот трамплин,
  • ti — длительность полета в секундах
  • pi — число, означающее сколько метров до трамплина Вася должен разбегаться, чтобы суметь приготовиться и прыгнуть с этого трамплина. В течение разбега Вася обязан ехать по снегу (то есть не должен находиться в полете), но его скорость все равно составляет один метр в секунду.

Васе разрешается двигаться в любом направлении оси X, но запрещается заходить за линию старта, то есть в отрицательную полуось. Вася сам выбирает, какими трамплинами он воспользуется и в каком порядке, то есть он не обязан пользоваться всеми трамплинами, которые находятся на его пути. В частности, Вася может проехать мимо трамплина. Гарантируется, что xi + di ≤ L, значит, Вася не сможет преодолеть линию финиша в полете.

Вася может прыгать на трамплине только в сторону положительного направления оси X. То есть, используя i-ый трамплин, он начинает разгон в точке xi - pi, прыгает в точке xi и приземляется в точке xi + di. В другую сторону прыгать не разрешается.

Ваша задача — найти минимальное время, которое потратит Вася, чтобы преодолеть дистанцию.

Входные данные

Первая строка входных данных содержит два целых числа n и L (0 ≤ n ≤ 105, 1 ≤ L ≤ 109). Далее в n строках находятся описания трамплинов, каждое описание находится на отдельной строке. Каждое описание — это четверка целых неотрицательных чисел xi, di, ti, pi (0 ≤ xi ≤ L, 1 ≤ di, ti, pi ≤ 109, xi + di ≤ L).

Выходные данные

Выведите в первую строку минимальное время в секундах, которое нужно Васе, чтобы преодолеть трассу. Во вторую строку выведите k — количество трамплинов, которыми нужно воспользоваться Васе, а в третью строку выведите k чисел — номера использованных трамплинов в порядке, в котором Вася их использовал. Каждый номер выводите ровно один раз, числа при выводе разделяйте пробелом. Трамплины нумеруются с 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
Примечание

В первом примере, Вася не сможет воспользоваться трамплином номер 2, потому что тогда он должен будет разбегаться, начиная с точки -3, что не разрешено условием. Оптимальный вариант — воспользоваться трамплином номер 1, итоговое время равно: движение до точки разбега + разбег до трамплина + время полета + движение до финиша = 0 + 5 + 5 + 5 = 15.

Во втором примере, Васе вообще не выгодно использовать трамплин номер 1, так как t1 > d1. Оптимальный вариант — воспользоваться трамплином номер 2, итоговое время равно: движение до точки разбега + разбег до трамплина + время полета + движение до финиша = 14 + 1 + 1 + 0 = 16.