Given $n$ intervals on the real axis, where the $i$-th interval is $[L_i, R_i]$ ($1 \leq i \leq n$). The $2n$ endpoints of these $n$ intervals are all distinct. From this, it follows that for any two of these $n$ intervals, their intersection is either empty or one is contained within the other.

Interval Subset Problem: For the given $n$ intervals $[L_i, R_i]$ ($1 \leq i \leq n$) on the real axis with distinct endpoints, select a sub-interval $[l_i, r_i]$ ($L_i \leq l_i < r_i \leq R_i$) from each interval $[L_i, R_i]$ such that the intersection of any two selected sub-intervals contains at most one point. The goal is to maximize the sum of the lengths of the $n$ selected sub-intervals, $\sum_{i=1}^n (r_i - l_i)$.

Input

The first line contains a positive integer $n$.

Each of the following lines contains two integers. The $(i+1)$-th line provides two integers $L_i, R_i$, representing the interval $[L_i, R_i]$.

Output

Output the calculated maximum sum of the lengths of the sub-intervals.

Examples

Input 1

4
1 10
2 3
5 9
6 7

Output 1

7

Subtasks

$10\%$ of the test data satisfies $n \leq 10$.

$40\%$ of the test data satisfies $n \leq 500$.

$100\%$ of the test data satisfies $n \leq 2\,000$.