Задача B. Поезда ≡

Автор:X Всероссийская олимпиада школьников   Ограничение времени:4 сек
Входной файл:train.in   Ограничение памяти:200 Мб
Выходной файл:train.out  

Условие

В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство железнодорожной компании решило изменить график движения поездов. Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения: сначала T1 минут поезд идет со скоростью V1 метров в минуту, затем T2 минут со скоростью V2 м/мин, ..., наконец, TN минут со скоростью VN м/мин. В течение интервала Ti (1 ≤ i ≤ N) поезд может стоять.

По действующей инструкции обеспечения безопасности движения расстояние между началами следующих друг за другом поездов никогда не должно быть менее L метров. Напишите программу, определяющую минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться по установленному графику без опасного сближения.

Формат входного файла

В первых двух строках входного файла содержатся натуральные числа, задающие минимально допустимое расстояние L и количество участков пути N. Далее следуют N пар целых чисел T1, V1, ..., TN, VN, описывающих график движения.

Формат выходного файла

В выходной файл требуется вывести искомый интервал между отправлениями поездов в минутах, не менее чем с тремя верными знаками после десятичной точки.

Ограничения

100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000, 1 ≤ Ti ≤ 1000, 0 ≤ Vi ≤ 1000.

Примеры тестов

№ Входной файл (train.in) Выходной файл (train.out)
1 
1000
4
10 0
30 80
15 0
20 100
 
27.5
0.025s 0.007s 15