Поезда
В связи с участившимся числом аварий на железнодорожной ветке Кострома-Судиславль, руководство железной дороги решило изменить график движения поездов. Тщательный анализ состояния железнодорожного полотна показал, что оптимальным является следующий график движения поездов с учётом остановок на станциях: сначала поезд идёт на протяжении t[1] минут со скоростью v[1] метров в минуту, затем t[2] минут со скоростью v[2] метров в минуту, ..., и наконец t[n] минут со скоростью v[n] метров в минуту. В течении некоторых интервалов поезд может стоять (скорость равна 0).
По действующей инструкции обеспечения безопасности движения поездов расстояние между локомотивами двух следующих друг за другом поездов должно быть не менее l метров. Определите минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться по этому графику без опасного сближения.
Входные данные
В первых двух строках содержатся два натуральных числа, задающих минимально допустимое расстояние l и количество участков пути n (100 ≤ l ≤ 10000, 1 ≤ n ≤ 10000). Далее следует n пар целых чисел t[i] и v[i] (1 ≤ t[i] ≤ 1000, 0 ≤ v[i] ≤ 1000), задающих график движения поездов.
Выходные данные
Вывести искомый интервал между отправлениями поездов в минутах, не менее чем с тремя десятичными знаками.