У зв'язку з тим, що почастішали аварії на залізничній вітці Кострома-Судиславль, керівництво залізниці вирішило змінити графік руху потягів. Ретельний аналіз стану зілізничного полотна показав, що оптимальним є наступний графік руху потягів з врахуванням зупинок на станціях: спочатку потяг йде протягом t1 хвилин зі швидкістю v1 метрів за хвилину, потім t2 хвилин зі швикістю v2 метрів за хвилину, ..., нарешті tn хвилин зі швидкістю vn метрів за хвилину. Протягом деяких інтервалів потяг може стояти (швидкість дорівнює 0).

За діючою інструкцією забезпечення безпеки руху потягів відстань міжу локомотивами двох слідуючих один за одним потягів повинна бути не менше l метрів. Визначте мінімально допустимий інтервал в хвилинах між відправленями потягів, який дозволяє їм рухатись за цим графіком без небезпечного зближення.

Вхідні дані

У перших двох рядках міститься два натуральних числа, які задають мінімально допустиму відстань l та кількість ділянок шляху n (100 ≤ l ≤ 10000, 1 ≤ n ≤ 10000). Далі йде n пар цілих чисел ti та vi (1 ≤ ti ≤ 1000, 0 ≤ vi ≤ 1000), які задають графік руху потягів.

Вихідні дані

Вивести шуканий інтервал між відправленнями потягів у хвилинах, не менше ніж з трьома десятковими знаками.