Болеющие коровы решили помочь Фермеру Джону.
Для того, чтобы ограничить передачу болезни, N (2 ≤ N ≤ 10
5) коров ФД решили попрактиковаться в "социальном дистанцировании" и "распределились" по ферме. Ферма представлена в виде прямой линии, с M взаимно не имеющими общих точек интервалами (1 ≤ M ≤ 10
5), на которых растёт трава. Коровы хотят расставиться в точках с различными координатами, каждая точка покрыта травой, так, чтобы максимизировать значение D. Где D представляет расстояние между ближайшей парой коров. Помогите коровам определить наибольшее значение D.
Входные данные
Первая строка ввода содержит N и M. Каждая из следующих M строк описывает интервал двумя целыми числами a и b, где 0 ≤ a ≤ b ≤10
18. Никакие два интервала не перекрываются и не касаются своими конечными точками. Корова, стоящая на конечной точке интервала считается стоящей на траве.
Выходные данные
Выведите наибольшее возможное значение D такое, что все пары коров не менее чем на D единиц друг от друга. Гарантируется, что существует решение с D>0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3
0 2
4 7
9 9 |
2 |