给定实轴上 n 个区间,第 i 个区间为 [Li,Ri] (1≤i≤n)。这 n 个区间的 2n 个区间端点互不相同。由此可知,这 n 个区间中,任何 2 个区间或其交集为空,或有包含关系。
区间子集问题:对于实轴上给定的区间端点互不相同的 n 个区间 [Li,Ri] (1≤i≤n),从每个子区间 [Li,Ri] 中选取一个子区间 [li,ri] (Li≤li<ri≤Ri),使得选出的任何 2 子区间的交集最多只有 1 个点。要求选出的 n 个子区间的长度之和 ∑ni=1(ri−li) 达到最大。
输入格式
第一行为一个正整数 n。
接下来每行有两个整数,第 i+1 行给出两个整数 Li,Ri,表示相应区间为 [Li,Ri]。
输出格式
输出计算出的最大子区间的长度和。
样例数据
样例输入
4
1 10
2 3
5 9
6 7
样例输出
7
子任务
测试数据中 10% 的数据满足 n≤10 。
测试数据中 40% 的数据满足 n≤500 。
测试数据中 100% 的数据满足 n≤2000 。