该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

Format

Input

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

Output

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

Samples

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

16

Limitation

对于 100%的数据，0 ≤ n ≤ 10000；0 ≤ p < k ≤ 30000。