You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

农场主约翰为他的奶牛们开设了一个游泳池，他认为这将有助于奶牛放松并产出更多牛奶。

为确保安全，他雇佣了(N)头奶牛担任救生员，每头奶牛都有一个班次，涵盖一天中某个连续的时间段。为简化起见，游泳池每天从(t = 0)时刻开放到(t = 1000)时刻，所以每个班次可以用两个整数来描述，即奶牛开始和结束班次的时间。例如，一头从(t = 4)时刻开始、(t = 7)时刻结束班次的救生员负责三个单位时间（注意，端点在时间上是“点”）。

不幸的是，农场主约翰雇佣的救生员比他资金所能支持的多了(1)头。已知他必须恰好辞退一名救生员，那么剩余救生员的班次所能覆盖的最长时间是多少呢？如果至少有一名救生员在场，那么这个时间段就被视为有覆盖。

输入格式

输入的第一行包含(N)（(1 \leq N \leq 100)）。接下来(N)行中的每一行都通过两个取值范围在(0)到(1000)之间的整数来描述一名救生员，这两个整数分别表示该救生员班次的起始点和结束点。所有这些端点都各不相同。不同救生员的班次可能会重叠。

输出格式

请写出一个数字，表示如果农场主约翰辞退一名救生员，剩余救生员仍能覆盖的最长时间。

样例 #1

样例输入 #1

3
5 9
1 4
3 7

样例输出 #1

7