配点 : $1000$ 点

問題文

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

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

制約

• 入力は全て整数である。
• $1 \leq N \leq 10^5$
• $1 \leq l_i

部分点

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

入力

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

$N$

$l_1$ $r_1$

$l_2$ $r_2$

:

$l_N$ $r_N$

出力

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

3
1 3
5 7
1 3

2

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

3
2 5
4 6
1 4

0

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

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

1999999680

5
123456 789012
123 456
12 345678901
123456 789012
1 23

246433

1
1 400

0