Задача Бизнес центр

Описание

Международная корпорация Cyber полис построила новый мега-высокий бизнес-центр для своих сотрудников а так же для сдачи помещения в аренду. Здание имеет так много этажей, что это непрактично иметь отдельную кнопку для каждого этажа в каждой кабинке лифта. Вместо этого, в каждый лифт имеет всего две кнопки. Одна кнопка в i-том элеваторе поднимает лифт на u _i этажей, другая опускает на d _i этажей. Бизнес-центр является настолько высоким, что мы можем игнорировать его высоту в этой задачи (вы никогда не достигните верхнего этажа), но вы не можете опустится ниже нулевого этажа.

Вы начинаете на нулевом этаже бизнес-центра. Вы должны выбрать одну кабинку лифта из m кабинок для передвижения. После выбора вы не можете сменить кабинку. Требуется определить - какой самый низкий этаж выше земли на который вы можете попасть нажав кнопку лифта ровно n раз?

Формат входных данных

Первая строка входного файла содержит два числа n, m (1 ≤ n ≤ 1 000 000, 1 ≤ m ≤ 2 000) - количество нажатий кнопок и количество кабинок. Следующие m строк описывают кабинки лифта. Каждая строка содержит два числа u _i и d _i (1 ≤ u _i , d _i ≤ 1 000).

Формат выходных данных

В выходной файл выведите одно положительное число - номер самого низкого этажа выше земли на который можно попасть на одном из m элеваторов, нажав кнопку лифта ровно n раз.