Codeforces Round 101 (Div. 2) |
---|
Закончено |
Вася участвует в лыжной гонке по оси X. Старт находится в точке 0, а финиш — в точке L, то есть на расстоянии L метров от старта в положительном направлении оси. Вася так сильно натренирован, что может пробежать один метр ровно за одну секунду.
Кроме того, на трассе расположено n трамплинов, каждый трамплин характеризуется четырьмя числами:
Васе разрешается двигаться в любом направлении оси 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.
Название |
---|