В связи с увеличившимся количеством аварий на железной дороге, руководство дороги решило изменить график движения поездов. Анализ состояния полотна дороги показал, что оптимальным является следующий график движения: сначала T
1 минуту поезд идет со скоростью V
1 метр в минуту, потом T
2 минуты со скоростью V
2 метра в минуту, ..., наконец, T
N минут со скоростью V
N метрв в минуту. При этом на любом из этих участков поезд может стоять (V
i = 0).
По действующей инструкции обеспечения безопасности движения расстояние между началами двух следующих друг за другом поездов не должно превышать L метров. Напишите программу, которая по этим данным определяет минимально допустимый интервал в минутах между отправлениями поездов, позволяющий им двигаться без опасного сближения.
Входные данные
Первые две строки входных данных содержат числа L и N (100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000). Далее идет N строк, задающих график движения поезда, каждая строка содержит пару чисел T
i и V
i (1 ≤ T
i ≤ 1000, 0 ≤ V
i ≤ 1000).
Выходные данные
Требуется вывести минимально допустимый интервал отправления поездов в минутах, с не менее, чем тремя знаками после точки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1000
4
10 0
30 80
15 0
20 100
|
27.5000
|