Соціальна дистанція#10307
Фермер Джон стурбований здоров'ям своїх корів через спалах дуже заразної хвороби великої рогатої худоби COWVID-19.
Щоб зменшити ризик передачі хвороби, корів фермера Джона вирішили практикувати "соціальне дистанціювання" і розосередитися по фермі. Ферма представлена у вигляді числової лінії з взаємно неперетинними інтервалами, в яких є трава для випасу. Корови хочуть розташуватися в різних цілих точках, кожна з яких покрита травою, щоб максимізувати значення , де — це відстань між найближчою парою корів. Допоможіть коровам визначити максимально можливе значення .
Перший рядок містить (2 \le n \le 10^5) і (1 \le m \le 10^5). Кожен з наступних рядків описує інтервал у вигляді двох цілих чисел і , де 0 \le a \le b \le 10^{18}. Жодні два інтервали не перекриваються і не торкаються в своїх кінцевих точках. Корова, що стоїть у кінцевій точці інтервалу, вважається такою, що стоїть на траві.
Виведіть максимально можливе значення , таке, щоб усі пари корів знаходилися на відстані не менше одиниць одна від одної. Рішення з d > 0 гарантовано існує.
Один зі способів досягти d = 2 - це розмістити корів у позиціях , , , і .
Приклад 1