当前没有测试数据。

题目描述

随着数字阅读的普及，某市图书馆决定开放一个全天候的数字资源中心，以供市民随时访问电子书籍和在线资料。为了确保访问系统的顺畅和安全，图书馆聘请了若干名技术人员轮流值班，监控系统运行情况。

技术人员每天工作的时间时间从 $t = 0$ 到 $t = 1000$。每位技术人员的工作班次可以用一对时间区间来表示。例如，技术人员在 $T_1 = 1$ 开始上班，到 $T_2 = 8$ 下班，则该班次覆盖了 $7$ 个时间单位的值班。（请注意：下班的时间点不包含在班次内，即 $[T_1, T_2)$ 表示员工的工作时间范围）

由于预算问题，图书馆领导发现他们聘请的人数超过了预算所能承受的范围，需要解雇一名技术人员。在确保数字资源中心尽可能长时间有人值守的前提下，领导需要你帮忙计算在解雇任意一名技术人员后，剩余技术人员可以覆盖的最大时间长度。

输入格式

第一行，读入一个整数 $N$，表示技术人员的数量。

接下来的 $N$ 行，每行两个整数 $T_1$ 和 $T_2$，分别代表一个技术人员班次的开始和结束时间。

输出格式

输出一个整数，表示在解雇一名技术人员后，剩余技术人员的班次所能覆盖的最大时间长度。

样例

输入

3
1 5
2 6
9 12

输出

7

输入

5
124 200
189 298
275 580
46 238
373 651

输出

605

输入

5
0 102
900 1000
105 200
189 280
300 600

输出

597

数据范围

对于 $10\%$ 的测试数据，满足 $1 \le N \le 10$。

对于 $100\%$ 的数据，满足 $1 \le N \le 100$，$0 \le T_i \le 1000$。