We have many lectures to be held in a lecture hall. Each lecture is uniquely determined by its start and end time. If two lectures have overlapping or partially overlapping times, they cannot be held in the lecture hall at the same time. We want to maximize the utilization of this lecture hall, which means we need to select a set of non-overlapping lectures such that the total duration of these lectures is as long as possible. We assume that one lecture can start immediately at the moment another one ends.

Input

The first line of the input contains a positive integer $n$, where $n \le 10000$, representing the total number of lectures. Each of the following $n$ lines contains two space-separated integers $p$ and $k$, where $0 \le p < k \le 30000$. Such a pair of integers represents a lecture starting at time $p$ and ending at time $k$.

Output

Output a single integer representing the maximum total duration of the lectures.

Examples

Input 1

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

Output 1

16