QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[-11]

# 6178. 区间子集问题

Statistics

给定实轴上 n 个区间,第 i 个区间为 [Li,Ri] (1in)。这 n 个区间的 2n 个区间端点互不相同。由此可知,这 n 个区间中,任何 2 个区间或其交集为空,或有包含关系。

区间子集问题:对于实轴上给定的区间端点互不相同的 n 个区间 [Li,Ri] (1in),从每个子区间 [Li,Ri] 中选取一个子区间 [li,ri] (Lili<riRi),使得选出的任何 2 子区间的交集最多只有 1 个点。要求选出的 n 个子区间的长度之和 ni=1(rili) 达到最大。

输入格式

第一行为一个正整数 n

接下来每行有两个整数,第 i+1 行给出两个整数 Li,Ri,表示相应区间为 [Li,Ri]

输出格式

输出计算出的最大子区间的长度和。

样例数据

样例输入

4
1 10
2 3
5 9
6 7

样例输出

7

子任务

测试数据中 10% 的数据满足 n10

测试数据中 40% 的数据满足 n500

测试数据中 100% 的数据满足 n2000