问题描述

给定一个包含 $N$ 个节点的无向图，每个节点上分配了一个半开区间。节点 $i$ 上的区间为 $\[l_i, r_i)$。

尼玛君根据以下规则添加了边：

• 如果两个节点 $i$ 和 $j$ 上的区间 有交集，则添加一条连接节点 $i$ 和节点 $j$ 的边。
• 添加的边的长度等于两个区间的交集的长度。

请计算最小生成树中包含的边的总长度。如果不存在最小生成树，则输出 -1。

约束条件

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

输入

输入由标准输入给出，具有以下格式。

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

输出

请输出结果。

示例1

3
1 4
2 6
3 4

输出示例1

2

示例2

2
1 1000
1000 2000

输出示例2

-1

示例3

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

输出示例3

387

示例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

输出示例4

409