Социальная дистанция
Фермер Джон беспокоится о здоровье своих коров после вспышки очень заразной болезни крупного рогатого скота COWVID-19.
Чтобы ограничить передачу болезни, n коров фермера Джона решили практиковать "социальное дистанцирование" и рассредоточиться по ферме. Ферма имеет форму числовой линии с m взаимно непересекающимися интервалами, в которых есть трава для выпаса. Коровы хотят расположиться в различных целых точках, каждая из которых покрыта травой, чтобы максимизировать значение d, где d представляет собой расстояние между ближайшей парой коров. Помогите коровам определить максимально возможное значение d.
Входные данные
Первая строка содержит n (2 ≤ n ≤ 10^5) и m (1 ≤ m ≤ 10^5). Каждая из следующих m строк описывает интервал в виде двух целых чисел a и b, где 0 ≤ a ≤ b ≤ 10^18. Никакие два интервала не перекрываются или не касаются в своих конечных точках. Корова, стоящая в конечной точке интервала, считается стоящей на траве.
Выходные данные
Выведите такое максимально возможное значение d, чтобы все пары коров находились на d единицах друг от друга. Решение с d > 0 гарантированно существует.
Пример
Один из способов добиться d = 2 - это держать коров в позициях 0, 2, 4, 6 и 9.
