Mô tả và yêu cầu

Dọc theo bờ sông tuyệt đẹp chạy ngang qua thành phố, có 𝑛 người đứng tập thể
dục vào các buổi sáng hàng ngày.

Bờ sông có 𝑚 đoạn được lát gạch có thể đứng tập thể dục, các vị trí khác được
trồng hoa vì vậy không thể đứng tập thể dục được. Để đơn giản có thể mô tả các đoạn
này như các đoạn thẳng không giao nhau trên trục toạ độ. Mỗi người tập thể dục sẽ đứng
tại vì trí toạ độ nguyên của một đoạn bờ sông được lát gạch sao cho giá trị 𝑑 là lớn nhất.
Với 𝑑 là khoảng cách giữa hai người tập thể dục đứng gần nhau nhất.

Yêu cầu: Hãy tìm giá trị lớn nhất của 𝑑.

Dữ liệu: Vào từ file văn bản KCACH.INP gồm:
 Dòng 1: Hai số nguyên dương 𝑛, 𝑚 (2 ≤ 𝑛 ≤ 105; 1 ≤ 𝑚 ≤ 105).
 Dòng 2. .𝑚 + 1: Dòng thứ 𝑖 chứa hai số nguyên 𝑎𝑖,𝑏𝑖 xác định đoạn bờ sông
[𝑎𝑖, 𝑏𝑖] được lát gạch, các đoạn này không giao nhau (|𝑎𝑖|, |𝑏𝑖| ≤ 109; 𝑎𝑖 ≤ 𝑏𝑖).

Kết quả: Ghi ra file văn bản KCACH.OUT gồm:

 Một số nguyên là giá trị lớn nhất của 𝑑, dữ liệu luôn đảm bảo có lời giải 𝑑 > 0.

Ví dụ

KCACH.INP                      KCACH.OUT
                      5 3                            2
                      0 2
                      4 7
                      9 9
Ràng buộc:
       30% số test có 𝑚      ≤   103, |𝑎𝑖|, |𝑏𝑖|  ≤  103.
       30% số test có 𝑚      ≤   105, 𝑎𝑖  =  𝑏𝑖.
       40% số test còn lại không giới hạn gì thêm.