Задача №743. Поезда
В связи с увеличившимся количеством аварий на железной дороге руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T1 минут поезд идет со скоростью V1 метров в минуту, потом T2 минут со скоростью V2 метров в минуту, ..., наконец, TN минут со скоростью VN метров в минуту. При этом на любом из этих участков поезд может стоять (Vi = 0).
По действующей инструкции обеспечения безопасности движения расстояние между началами двух следующих друг за другом поездов должно быть не менее L метров. Напишите программу, которая по этим данным определяет минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться без опасного сближения.
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел Ti и Vi (1 ≤ Ti ≤ 1000, 0 ≤ Vi ≤ 1000).
Требуется вывести минимально допустимый интервал отправления поездов в минутах не менее чем с тремя знаками после точки.
1000 4 10 0 30 80 15 0 20 100
27.5000