Start 2023-01-12 14:00:00

USACO训练赛

End 2023-01-12 15:20:00
Contest is over.
Now 2024-03-05 00:01:08

A. 【USACO】Lifeguards(救生员)(USACO 2018)

Description

农场主约翰为他的奶牛开了一个游泳池,他认为游泳池能帮助他们放松,产更多的牛奶。为了确保安全,他雇佣了n头奶牛作为救生员,每头奶牛都有一个轮班,每天轮班的时间间隔是连续的。为了简单起见,池每天从时间t=0打开到时间t=1000,因此每个班次可以用两个整数描述,给出奶牛开始和结束班次的时间。例如,救生员从时间t=4开始,到时间t=7结束,涵盖三个时间单位(注意,终点是时间的“点”)。不幸的是,农场主约翰雇佣的救生员比他有足够的资金支持的还多。考虑到他必须解雇一名救生员,那么剩余救生员轮班的最大时间是多少?如果至少有一名救生员在场,则覆盖一段时间间隔。

Input

输入的第一行包含N(1≤n≤100)。接下来的n行中的每一行都以0…1000范围内的两个整数来描述一个救生员,给出救生员移位的起始点和结束点。所有这些端点都是不同的。不同救生员的换班可能会重叠。

Output

请写一个数字,给出如果农场主约翰解雇一名救生员仍能覆盖的最长时间。

Examples

Input

3
5 9
1 4
3 7

Output

7

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit