Задача . D. Трамплины

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

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

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

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

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

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