NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem21--阶梯教室设备利用

21: 阶梯教室设备利用

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定,如果两个演讲时间有部分或全部重复,那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室,也就是说,我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

请写一个程序:

读入所有演讲的起始和终止时间;

计算最大的可能演讲总时间;

Input

第一行包括一个正整数n,n<=10000,为所有的演讲的数目。以下的n行每行含有两个由空格隔开的整数p和k,0<=p< k<=30000。这样的一对整数表示一个演讲由时间p开始到时间k结束。

Output

输出唯一的一个整数,为最长的演讲总时间。


Sample Input Copy

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Sample Output Copy

16

HINT


Source/Category

其他