Как-то раз студент Данил поздно возвращался домой от трамвайной остановки по прямой дороге длины L. Остановка находится в точке x = 0, а дом Данила располагается в точке x = L. Данил идет от x = 0 к x = L с постоянной скоростью не меняя направления.
На дороге находятся n фонарей, каждый из которых освещает некоторый непрерывный отрезок дороги. Все n освещенных отрезков не имеют общих точек.
Данил очень любит петь, поэтому во время прогулки он хочет многократно спеть свою любимую песню. Так как неосвещенные участки дороги вызывают у него опасение, то он поёт только тогда, когда идет по освещенным фонарями отрезкам.
За время однократного исполнения любимой песни Данил проходит расстояние p. Данил не может начать очередное исполнение, если отрезок пути во время исполнения не является полностью освещенным. Кроме того, если Данил взял паузу между двумя исполнениями, то он не будет петь, пока не пройдет отрезок пути длины хотя бы t. Формально,
- Данил может начать исполнение в точке x, только если каждая точка отрезка [x, x + p] является освещенной;
- Если Данил закончил исполнение в точке x + p, то следующее он может начать только в точке y такой, что y = x + p или y ≥ x + p + t, и удовлетворяющей пункту 1.
Синими полукругами отмечены исполнения песни. Обратите внимание, что как только Данил взял паузу в исполнении, он не пел на протяжении пути длины не менее t. Определите, какое наибольшее количество раз Данил сможет исполнить свою любимую песню по пути из точки x = 0 в точку x = L.
Обратите внимание, что Данил не прерывает исполнение песни, то есть, начав петь в очередной раз, он заканчивает петь, пройдя путь длины p с момента начала исполнения.