Велосипедный спорт
На велосипедной прогулке по городу значительное количество времени уходит на ожидание светофоров. Если бы только можно было сократить это потерянное время, возможно, вы бы наконец-то успели на первую лекцию.
Обратите внимание, что время, потерянное на красный свет светофора, включает не только само ожидание. После того как свет становится зеленым, теряется дополнительное время на разгон велосипеда.
В этой задаче мы рассматриваем теоретическую модель велосипедной поездки, основанную на следующих правилах:
Велосипед движется вперед или стоит на месте, но никогда не движется назад. Велосипед не имеет максимальной скорости, но вы можете быть уверены, что релятивистские эффекты в этой задаче не будут задействованы.
Велосипед может увеличивать скорость с максимальным ускорением 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 знаков после запятой.
Тестовые случаи будут такими, что очень небольшие неточности не вызовут ошибок в окончательном ответе после округления.