Бізнес-центр
Міжнародна корпорація кіберполіції (ICPC) збудувала новий надвисокий бізнес-центр, щоб розмістити свою штаб-квартиру та здавати частину приміщень в оренду для додаткового прибутку. У ньому так багато поверхів, що недоцільно мати окрему кнопку в кожному з m ліфтів для кожного поверху. Замість цього, кожен ліфт має лише дві кнопки: одна в i-му ліфті піднімає його на u_i поверхів вгору, а інша опускає на d_i поверхів вниз. Бізнес-центр настільки високий, що ми можемо ігнорувати його висоту для цієї задачі (ви ніколи не досягнете верхнього поверху), але ви не можете опуститися нижче нульового поверху. Всі поверхи нумеруються цілими числами, починаючи з нуля, де нульовий - це перший поверх.
Ви починаєте з нульового поверху бізнес-центру. Вам потрібно вибрати один з m ліфтів, щоб піднятися на ньому. Після цього ви не можете змінити ліфт. Який найнижчий поверх вище нульового, на який ви можете потрапити після того, як натиснете кнопки ліфта рівно n разів?
Вхідні дані
Перша строка вхідного файлу містить два цілі числа n та m (1 <= n <= 1 000 000, 1 <= m <= 2000) – кількість натискань кнопок та кількість ліфтів на вибір. Наступні m рядків описують ліфти. Кожен рядок містить два цілі числа u_i та d_i (1 <= u_i, d_i <= 1 000).
Вихідні дані
Виведіть одне додатне ціле число – номер найнижчого поверху вище нульового, якого можна досягти одним з m ліфтів після натискання його кнопок рівно n разів.