問題文

1 から N までの番号がついた N 頂点の無向グラフが与えられます。 はじめ、このグラフに辺はありません。

各頂点には半開区間が割り当てられており、頂点 i には [l_i, r_i) が割り当てられています。

ニワンゴくんは以下のルールで辺を追加しました。

• 2 つの頂点 i, j に割り当てられた 2 つの区間が 共通部分を持つ ならば頂点 i, j をつなぐ辺を追加する
• 追加される辺の長さは 2 つの区間の共通部分の長さである

このグラフの最小全域木に含まれる辺の長さの総和を求めてください。最小全域木が存在しないならば代わりに -1 を出力してください。

制約

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

入力例1

3
1 4
2 6
3 4

作られるグラフは以下の図の通りです。

Sample input 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