← 返回题目列表

AtCoder · dwacon5th_final_c

C. 间隔和 MST

中文机器翻译题面 查看原题

配点 : 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