配点 : 1400 点
問題文
1 到 N 编号最多为 N 给你一个无向的顶点图。 最初,该图没有边。
每个顶点被分配一个半开区间,并且该顶点 i 有 已分配 [l_i, r_i) 。
Niwango-kun 使用以下规则添加了边缘。
- 2 顶点 分配给 i, j 分配给 2 间隔是 有通用零件 然后顶点 添加连接 i, j 的边
- 添加边的长度为 2 是两个区间的公共部分的长度
求该图的最小生成树中包含的边的长度之和。如果最小生成树不存在,则 -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
出力例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