Задача: Социальное дистанцирование

Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10⁵) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10⁵), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.

Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10¹⁸. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.

Примеры

Ваш ответ: