Problem Description

Given an undirected graph with $N$ vertices numbered from $1$ to $N$. Initially, there are no edges in the graph.

Each vertex is assigned a half-open interval, where vertex $i$ is assigned the interval $[l_i, r_i)$.

Niwango-kun added edges according to the following rules:

• If two vertices $i$ and $j$ have assigned intervals that overlap, an edge is added between vertices $i$ and $j$.
• The length of the added edge is the length of the overlapping part of the two intervals.

Find the sum of the lengths of the edges included in the minimum spanning tree (MST) of this graph. If an MST does not exist, output -1 instead.

Input Format

The input is given from the standard input in the following format:

$ N $ $ l_1 $ $ r_1 $ $ : $ $ l_{N} $ $ r_{N} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
1 4
2 6
3 4

Sample Output #1

2

Sample Input #2

2
1 1000
1000 2000

Sample Output #2

-1

Sample Input #3

7
121 951
420 492
197 607
167 925
438 717
200 986
104 483

Sample Output #3

387

Sample Input #4

14
319 1000
411 456
115 626
380 764
517 757
679 764
526 801
967 990
475 604
249 416
199 406
557 954
355 991
505 539

Sample Output #4

409

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq l_i < r_i \leq 10^9$

Sample Explanation 1

The graph constructed is as shown in the following figure:

见题面 Input 部分

见题面 Output 部分