Nông dân John lo lắng cho sức khỏe của những con bò sau khi căn bệnh truyền nhiễm rất mạnh ở bò COWVID-19 bùng phát.

Để hạn chế sự lây truyền của căn bệnh, \(N\) con bò của Nông dân John (\(2 \leq N \leq 10^5\)) đã quyết định thực hiện "giãn cách xã hội" và phân tán khắp trang trại. Trang trại có dạng một trục số một chiều, với \(M\) đoạn đôi một rời nhau (\(1 \leq M \leq 10^5\)) mà trên đó có cỏ để gặm. Những con bò muốn đứng tại các điểm nguyên phân biệt có cỏ, sao cho tối đa hóa giá trị \(D\), trong đó \(D\) là khoảng cách giữa cặp bò gần nhau nhất. Hãy giúp những con bò xác định giá trị \(D\) lớn nhất có thể.

Dữ liệu vào

Tệp socdist.in:

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đoạn bằng hai số nguyên \(a\) và \(b\), trong đó \(0 \leq a \leq b \leq 10^{18}\). Không có hai đoạn nào giao nhau hoặc tiếp xúc nhau tại đầu mút. Một con bò đứng tại đầu mút của một đoạn vẫn được tính là đứng trên cỏ.

Dữ liệu ra

Tệp socdist.out:

In ra giá trị \(D\) lớn nhất có thể sao cho mọi cặp bò đều cách nhau ít nhất \(D\) đơn vị. Đề bài đảm bảo tồn tại một cách xếp với \(D>0\).

Phân nhóm

• Các test 2–3 thỏa mãn \(b \leq 10^5\).
• Các test 4–10 không có ràng buộc bổ sung.

Ví dụ

5 3
0 2
4 7
9 9

2

Nguồn

USACO 2020 US Open Contest, Silver — Social Distancing

Tác giả bài: Brian Dean.