Câu 4. Robot (4,0 điểm; Đề TS vào 10 – Lào Cai 2026 – 2027)

Công ty LCROBO tổ chức kiểm tra tính năng sản phẩm của N robot. Mỗi lần kiểm tra nhân viên kỹ thuật sẽ cho những con robot đứng trên đường thẳng theo hàng ngang, no như một trục số nguyên. Để đảm bảo an toàn trong quá trình kiểm tra, các robot phải đứng cách xa nhau càng tốt. Trên đường thử, có một số đoạn đã bố trí trạm sạc nên robot không thể đứng vào những vị trí đó, những đoạn Robot có thể đứng được mô tả bởi M đoạn như nhau và đoạn thứ i được mô tả bằng hai số nguyên Ai, Bi. Robot có thể đứng tại một vị trí tọa độ nguyên trên những đoạn này. Gọi L là khoảng cách giữa hai robot đứng gần nhau nhất.
Yêu cầu: Hãy tìm giá trị lớn nhất của L để xếp đủ N robot trong một lần kiểm tra.
Dữ liệu vào:

• Dòng 1: Hai số nguyên dương N, M (2 ≤ N ≤ 10⁵; 1 ≤ M ≤ 10⁵) tương ứng là số robot và số đoạn mà robot có thể đứng.
• M dòng tiếp theo: Mỗi dòng chứa hai số nguyên Ai, Bi (0 ≤ Ai ≤ Bi ≤ 10¹⁸; 1 ≤ i ≤ M) xác định M đoạn robot có thể đứng được. Chú ý rằng các đoạn trên không giao nhau.

Kết quả: In ra giá trị lớn nhất của L. Chú ý rằng lời giải với L > 0 luôn tồn tại.
Ví dụ:

Dữ liệu vào	Kết quả	Giải thích
3 3 6 10 2 5 11 15	6	Không có trạm sạc nào nằm giữa các đoạn mà robot có thể đứng được. Vị trí đứng của 3 robot có thể là: 2, 8, và robot cuối cùng có thể đứng ở vị trí 14 hoặc 15.
5 4 0 2 15 21 4 7 11 12	5	Vị trí đứng của 5 robot có thể là: 0, 5, 11, 16, 21.
3 2 8 9 2 5	3	Vị trí đứng của 3 robot có thể là: 2, 5 và robot cuối cùng có thể đứng ở vị trí 8 hoặc 9.

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài với trường hợp không có trạm sạc nào nằm giữa các đoạn mà robot có thể đứng được.
• Có 30% số test tương ứng với 30% số điểm của bài với 100 ≤ N ≤ 10³; 1 ≤ M ≤ 10³; 0 ≤ A_i ≤ B_i ≤ 10⁶; 1 ≤ i ≤ M;
• Có 40% số test còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.