题目描述

Farmer John 为他的奶牛们开设了一个游泳池，他认为这将帮助他们的奶牛放松并生产更多的牛奶。

为了确保安全，他聘请了 $N$ 头奶牛作为救生员，每个救生员在一天中的工作时间都是一段连续时间。简单来说，游泳池每天在时刻 $t = 0$ 时开放，在时刻 $t = 1000$ 时关闭，救生员的工作时间可以用两个整数来描述，分别表示开始工作和结束工作的时刻。比方说，一个救生员在时刻 $t = 4$ 时开始工作，在时刻 $t = 7$ 时结束工作，因此他的工作时长为 $3$ 个单位时间。

不幸的是， Farmer John 的资金不太充裕。请问当他必须要解雇一名救生员时，剩下的救生员能覆盖的最大时间是多少？一段时间被覆盖当且仅当有至少一名救生员在泳池中。

输入格式

输入的第一行包含一个整数 $N$ （ $1 \le N \le 100$ ）。

接下来 $N$ 行，每行有两个取值范围在 $[0, 1000]$ 的整数，给出了每个救生员开始和结束工作的时刻，所有时刻都是不相同的，不同救生员的工作时间可能会重叠。

输出格式

输出一个整数，表示如果 Farmer John 解雇一名救生员后，剩下的救生员能覆盖的最大时间。

3
5 9
1 4
3 7

7

提示