Фермер Джон турбується за здоров'я своїх корів після вибуху високорозповсюдженої хвороби худоби COWVID-19.

Для обмеження передачі хвороби ~N~ корів фермера Джона (~2 \leq N \leq 10^5~) вирішили практикувати "соціальну дистанцію" та розійшлись по фермі. Ферма має форму 1D числової лінії, з ~M~ не перетинаючимися інтервалами (~1 \leq M \leq 10^5~), де є трава для пасовища. Корови хочуть розташуватися в різних цілих точках, кожна з яких покрита травою, щоб максимізувати значення ~D~, де ~D~ представляє відстань між найближчою парою корів. Будь ласка, допоможіть коровам визначити найбільше можливе значення ~D~.

Input

Перший рядок введення містить ~N~ та ~M~. Наступні ~M~ рядків описують кожен інтервал у вигляді двох цілих чисел ~a~ і ~b~, де ~0 \leq a \leq b \leq 10^{18}~. Жодні два інтервали не перекриваються і не дотикаються до своїх кінцівок. Корова, що стоїть на кінці інтервалу, рахується, як стояча на траві.

Output

Виведіть найбільше можливе значення ~D~ таке, щоб всі пари корів були віддалені на ~D~ одиниць. Гарантується наявність рішення з ~D>0~.

Оцінювання

Ви отримаєте ~20~ балів, якщо рішення буде працювати правильно для ~b\le 10^5~.

Sample Input 1

5 3
0 2
4 7
9 9

Sample Output 1

2

Notes

Один із способів досягнення ~D=2~ - мати корови на позиціях ~0~, ~2~, ~4~, ~6~ та ~9~.