Фермер Джон беспокоится за здоровье своих коров после вспышки очень заразной болезни крупного рогатого скота COWVID-19.

Чтобы ограничить передачу болезни, n коров фермера Джона решили практиковать "социальное дистанцирование" и рассредоточиться по ферме. Ферма имеет форму числовой линии с m взаимно непересекающимися интервалами, в которых есть трава для выпаса. Коровы хотят расположиться в различных целых точках, каждая из которых покрыта травой, чтобы максимизировать значение d, где d представляет собой расстояние между ближайшей парой коров. Помогите коровам определить максимально возможное значение d.

Входные данные

Первая строка содержит n (2 ≤ n ≤ 105) и m (1 ≤ m ≤ 105). Каждая из следующих m строк описывает интервал в виде двух целых чисел a и b, где 0 ≤ a ≤ b ≤ 1018. Никакие два интервала не перекрываются или не касаются в своих конечных точках. Корова, стоящая в конечной точке интервала, считается стоящей на траве.

Выходные данные

Выведите такое максимально возможное значение d, чтобы все пары коров находились на d единицах друг от друга. Решение с d > 0 гарантированно существует.

Пример

Один из способов добиться d = 2 - это держать коров в позициях 0, 2, 4, 6 и 9.