Задача №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