Cho N đoạn thẳng có các đầu mút đánh dấu trên trục số là [Li,Ri], i=1..N (Li,Ri có giá trị tuyệt đối nhỏ hơn 32.000). Viết chương trình tìm đoạn trục số được phủ liên tiếp dài nhất bởi các đoạn thẳng đã cho?
Dữ liệu vào
- Dòng đầu là số N (1<N<=10.000)
- N dòng tiếp theo mỗi dòng biểu diễn đầu mút các đoạn thẳng là Li và Ri (mỗi số cách nhau một dấu cách).
Kết quả
Một dòng duy nhất ghi độ dài liên tiếp lớn nhất trên trục số mà các đoạn thẳng đã phủ được.
Input
7
7 12
0 5
20 25
33 38
6 8
27 34
11 19
Output
13
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài có 1<N<=1000.
- Có 30% số test ứng với 30% số điểm của bài có 1000<N<=5000.
- Có 40% số test ứng với 40% số điểm của bài có 5000<N<=10000.
Nguồn: DBBB14 CVA-HN