Задача №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
Сдать: для сдачи задач необходимо войти в систему