Велоспорт
На велосипедній прогулянці містом значна частина часу витрачається на очікування світлофорів. Якби ви могли скоротити цей втрачений час, можливо, нарешті встигли б на першу лекцію.
Зверніть увагу, що час, втрачений на червоному світлофорі, включає не лише час, проведений у стані спокою біля світлофора. Після того, як світло стає зеленим, додатковий час витрачається на розгін велосипеда.
У цій задачі ми розглядаємо теоретичну модель велосипедної поїздки, засновану на таких правилах:
Велосипед рухається вперед або стоїть на місці, але ніколи не рухається назад. Велосипед не має максимальної швидкості, але ви можете бути впевнені, що релятивістські ефекти в цій задачі не враховуються.
Велосипед може збільшувати швидкість з максимальним прискоренням 0.5 метрів на секунду в квадраті.
Велосипед може миттєво зменшити свою швидкість до будь-якого значення між нулем і поточною швидкістю.
Велосипед не може проїжджати на червоне світло.
Кожен світлофор змінює червоне і зелене світло за фіксованим, безперервно повторюваним ритмом. (Ці світлофори не змінюються на жовте світло.)
Очевидно, що теоретична модель відрізняється від реальності в кількох аспектах. Наприклад, голландські велосипедисти майже ніколи не зупиняються на червоне світло. Також, змодельований велосипед може гальмувати з нескінченною швидкістю, тоді як більшість студентських велосипедів не мають жодних гальмівних можливостей, про які можна говорити. Ми ігноруємо ці відмінності зараз і зосереджуємося на теорії.
Задача
Ви стоїте з велосипедом у точці X = 0 в момент часу T = 0 з нульовою швидкістю.
Ви дуже поспішаєте і хочете дістатися до точки X = X_dest якомога швидше.
Ваше завдання - знайти схему прискорення і гальмування так, щоб безпечно проїхати всі світлофори і прибути в X_dest у найраніший можливий час.
Дозволено гальмувати і/або зупинятися в будь-який момент під час поїздки, включаючи (звичайно) червоні світлофори. Однак, може бути більш ефективним знайти спосіб, за допомогою якого ви можете проїхати повз світлофори, коли вони зелені.
Вхідні дані
Вхідні дані для кожного тестового випадку складаються з наступних елементів:
Рядок, що містить дійсне число X_dest та ціле число L. X_dest - це загальна відстань для подолання в метрах (1 ≤ X_dest ≤ 10000); L - кількість світлофорів, які потрібно проїхати (0 ≤ L ≤ 10).
L рядків, що описують світлофори, наведені в порядку зростання позиції X. Кожен з цих рядків містить 3 дійсних числа:
X_i, позиція світлофора в метрах від початку (0 < X_i < X_dest);
R_i, тривалість кожного періоду червоного світла цього світлофора в секундах (10 ≤ R_i ≤ 500);
G_i, тривалість кожного періоду зеленого світла цього світлофора в секундах (10 ≤ G_i ≤ 500).
Усі світлофори стають червоними в момент часу T = 0.
Світлофор i вперше стає зеленим у момент часу T = R_i.
Ніколи не буває більше одного світлофора в одній і тій же позиції.
Вихідні дані
Для кожного тестового випадку напишіть один рядок виходу, що містить дійсне число: найраніший час, коли велосипедист може досягти пункту призначення.
Відповідь повинна бути округлена до 3 знаків після коми.
Тестові випадки будуть такими, що дуже малі неточності не викличуть помилок у кінцевій відповіді після округлення.