Соціальна дистанція
Фермер Джон стурбований здоров'ям своїх корів через спалах дуже заразної хвороби великої рогатої худоби 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.
