3932: P1697 [USACO18JAN] Lifeguards B

Farmer John 为他的奶牛们开设了一个游泳池，认为这将帮助它们放松并产更多的奶。 为了确保安全，他雇佣了 N 头奶牛作为救生员，每头奶牛的班次覆盖一天中的某个连续时间段。为简单起见，游泳池每天从时间 t=0 开放到时间 t=1000，因此每个班次可以用两个整数描述，分别表示奶牛开始和结束其班次的时间。例如，一头救生员从时间 t=4 开始到时间 t=7 结束，覆盖了 3 个单位的时间（注意端点表示时间点）。 不幸的是，Farmer John 多雇佣了 1 名救生员，超出了他的资金支持范围。鉴于他必须解雇恰好 1 名救生员，剩下的救生员的班次能够覆盖的最长时间是多少？如果至少有一名救生员在场，则某个时间段被视为被覆盖。

第一行：N (1 ≤ N ≤ 100) 接下来 N 行：每行两个整数，表示救生员班次的开始和结束时间，范围在 0...1000。所有端点都是唯一的。不同救生员的班次可能会重叠

一个数字，表示如果 Farmer John 解雇 1 名救生员后，剩下的救生员的班次能够覆盖的最长时间

3
5 9
1 4
3 7

7