Задача Wagon. Водій-далекобійник їде своєю фурою по довгій прямій дорозі з багатьма світлофорами. Для кожного світлофора він знає, як довго буде горіти червоне і зелене світло (цикл повторюється нескінченно).
Коли водій починає свою поїздку, всі світлофори горять червоним і тільки що розпочали свій цикл. Фура рухається рівномірно зі швидкістю в одну одиницю шляху в секунду, зупиняється і стартує миттєво, а жовте світло у даного типу світлофорів відсутнє. Коли світлофор червоний, фура миттєво зупиняється і чекає, поки не ввімкнеться зелене світло, після чого миттєво розпочинає свій рівномірний рух. Напишіть програму яка визначає, скільки часу потрібно водієві, щоб досягти кінця дороги. Початок дороги має координату 0, кінець має координату L.
Технічні умови Програма Wagon читає з пристрою стандартного введення два цілі числа N та L (1 ≤ N ≤ 104, 1 ≤ L ≤ 106), кількість світлофорів на дорозі та довжину дороги.
Кожен з наступних N рядків містить три цілі числа D, R і G, що описують один світлофор (1 ≤ D <L, 1 ≤ R ≤ 106, 1 ≤ G ≤ 106). D – координата світлофора,. R і G позначають тривалість відповідно червоного та зеленого сигналів. Світлофори впорядковані у порядку зростання D. Жодні 2 світлофори не мають однакової координати. Програма виводить на пристрій стандартного виведення час (у секундах), що потрібен водієві для подолання дороги.
Приклади
|
Введення 2 10 3 5 5 5 2 2
Виведення 12
|
Введення 4 30 7 13 5 14 4 4 15 3 10 25 1 1 Виведення 36 |