Bác nông dân John đã mở một hồ bơi cho đàn bò vì cho rằng nơi này sẽ giúp chúng thư giãn và sản xuất nhiều sữa hơn.

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

Không may, bác nông dân John đã thuê nhiều hơn khả năng chi trả đúng một nhân viên cứu hộ. Biết rằng ông phải sa thải đúng một nhân viên cứu hộ, thời lượng lớn nhất vẫn có thể được bao phủ bởi các ca trực của những nhân viên còn lại là bao nhiêu? Một khoảng thời gian được coi là có người trực nếu có ít nhất một nhân viên cứu hộ hiện diện.

Dữ liệu vào

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

Dữ liệu ra

In ra một số duy nhất là thời lượng lớn nhất vẫn có thể được bao phủ nếu bác nông dân John sa thải một nhân viên cứu hộ.

Ví dụ

3
5 9
1 4
3 7

7

Nguồn

USACO 2018 January Contest, Bronze — Lifeguards

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