Hiếu đã mở một bể bơi cho các con dê của mình. Để đảm bảo an toàn, ông thuê \(N\) con dê làm nhân viên cứu hộ, mỗi con có một ca trực bảo vệ một khoảng thời gian liên tục trong ngày. Để đơn giản, bể bơi mở cửa từ thời điểm \(t=0\) đến thời điểm \(t=1000\) hàng ngày, vì vậy mỗi ca trực có thể được mô tả bằng hai số nguyên, cho biết thời gian bắt đầu và kết thúc ca trực của một nhân viên cứu hộ. Ví dụ, một nhân viên cứu hộ bắt đầu lúc thời điểm \(t=4\) và kết thúc lúc thời điểm \(t=7\) bảo vệ ba đơn vị thời gian (lưu ý rằng điểm cuối là "các điểm" trong thời gian).

Thật không may, Hiếu đã thuê nhiều hơn một nhân viên cứu hộ so với ngân sách của mình. Cho biết nếu ông sa thải đúng một nhân viên cứu hộ, lượng thời gian tối đa vẫn có thể được bảo vệ bởi ca trực của các nhân viên cứu hộ còn lại là bao nhiêu? Một khoảng thời gian được coi là được bảo vệ nếu có ít nhất một nhân viên cứu hộ có mặt.

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa \(N\) \((1≤N≤100)\).
Mỗi dòng tiếp theo trong \(N\) dòng mô tả một nhân viên cứu hộ về hai số nguyên trong phạm vi \(0 \dots 1000\), cho biết điểm bắt đầu và kết thúc ca trực của nhân viên cứu hộ. Tất cả các điểm cuối như vậy đều khác biệt. Ca trực của các nhân viên cứu hộ khác nhau có thể chồng lấn.

OUTPUT FORMAT

In ra một số duy nhất, cho biết lượng thời gian tối đa vẫn có thể được bảo vệ nếu Hiếu sa thải 1 nhân viên cứu hộ

Ví dụ:

Input

3
5 9
1 4
3 7

Output

7

Giải thích ví dụ mẫu:

• Ví dụ 1:
  • Nếu sa thải nhân viên cứu hộ bảo vệ từ t=1 đến t=4, lượng thời gian tối đa được bảo vệ còn lại là 7 đơn vị.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House