Школа НТИ 2018. БД. Бинарная классификация

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство железнодорожной компании решило изменить график движения поездов. Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения: сначала T₁ минут поезд идет со скоростью V₁ метров в минуту, затем T₂ минут со скоростью V₂ м/мин, ..., наконец, T_N минут со скоростью V_N м/мин. В течение интервала T_i (1 ≤ i ≤ N) поезд может стоять.

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

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

В первых двух строках входного файла содержатся натуральные числа, задающие минимально допустимое расстояние L и количество участков пути N. Далее следуют N пар целых чисел T₁, V₁, ..., T_N, V_N, описывающих график движения.

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

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

Ограничения

100 ≤ L ≤ 10000, 1 ≤ N ≤ 1000, 1 ≤ T_i ≤ 1000, 0 ≤ V_i ≤ 1000.

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

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