Бізнес-центр#522

Бізнес-центр

1 секунда

64 мегабайти

Дуже легка

Міжнародна корпорація кіберполіції (ICPC) збудувала новий надвисокий бізнес-центр, щоб розмістити свою штаб-квартиру та здавати частину приміщень в оренду для додаткового прибутку. Тут стільки поверхів, що недоцільно мати окрему кнопку в кожному з $m$ ліфтів для кожного поверху. Натомість, кожен ліфт має лише дві кнопки: одна в $i$ -му ліфті піднімає на $u_{i}$ u_i поверхів вгору, а інша опускає на $d_{i}$ d_i поверхів вниз. Бізнес-центр настільки високий, що його висоту можна ігнорувати для цієї задачі (ви ніколи не досягнете верхнього поверху), але не можна опускатися нижче нульового поверху. Всі поверхи нумеруються цілими числами, починаючи з нуля, де нуль — це перший (нульовий) поверх.

Ви починаєте з нульового поверху бізнес-центру. Потрібно вибрати один з $m$ ліфтів і після цього змінювати ліфт не можна. Якого найнижчого поверху вище нульового ви можете досягти після того, як натиснете кнопки цього ліфта рівно $n$ разів?

Вхідні дані

Перший рядок вхідного файлу містить два цілих числа $n$ та $m$ ( $1 \leq n \leq 1000000$ 1 \le n \le 1\ 000\ 000, $1 \leq m \leq 2000$ 1 \le m \le 2000) — кількість натискань кнопок та кількість ліфтів на вибір. Наступні $m$ рядків описують ліфти. Кожен рядок містить два цілих числа $u_{i}$ u_i та $d_{i}$ d_i ( $1 \leq u_{i}, d_{i} \leq 1000$ 1 \le u_i, d_i \le 1\ 000).

Вихідні дані

Виведіть одне додатне ціле число — номер найнижчого поверху вище нульового, якого можна досягти одним з $m$ ліфтів після натискання його кнопок рівно $n$ разів.

Приклади

Приклад 1