問題文

シカのAtCoDeerくんは縦の長さが $1$ の細長い長方形が $N$ 個机に置いてあるのを見つけました。 机を二次元平面とみなすと、以下の図のように、$i(1≦i≦N)$ 個目の長方形は、縦は $$i-1,i$$ の範囲を、横は $$l_i,r_i$$ の範囲を占めています。

AtCoDeerくんはこの長方形をそれぞれ横に動かすことで、全ての長方形を連結にしようと考えました。 各長方形は横に距離 $x$ 動かすのに $x$ のコストがかかります。 全ての長方形を連結にするのに必要なコストの最小値を求めてください。 問題の制約のもとでこの値は整数になることが証明できます。

制約

• 入力は全て整数である。
• $1≦N≦10^5$
• $1≦l_i<r_i≦10^9$

部分点

• $1≦N≦400$, $1≦l_i<r_i≦400$ を満たすデータセットに正解した場合は、部分点として $300$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $l_1$ $r_1$ $l_2$ $r_2$ : $l_N$ $r_N$

出力

必要なコストの最小値を出力せよ。

入力例 1

3
1 3
5 7
1 3

出力例 1

2

$2$ 個目の長方形を左に $2$ 動かすのが最小です。

入力例 2

3
2 5
4 6
1 4

出力例 2

0

はじめから連結になっているため、動かす必要はありません。

入力例 3

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

出力例 3

1999999680

入力例 4

5
123456 789012
123 456
12 345678901
123456 789012
1 23

出力例 4

246433

入力例 5

1
1 400

出力例 5

0