E - NarrowRectangles Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

シカの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

Score : 1000 points

Problem Statement

AtCoDeer the deer found N rectangle lying on the table, each with height 1. If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected. For each rectangle, the cost to move it horizontally by a distance of x, is x. Find the minimum cost to achieve connectivity. It can be proved that this value is always an integer under the constraints of the problem.

Constraints

  • All input values are integers.
  • 1≤N≤10^5
  • 1≤l_i<r_i≤10^9

Partial Score

  • 300 points will be awarded for passing the test set satisfying 1≤N≤400 and 1≤l_i<r_i≤400.

Input

The input is given from Standard Input in the following format:

N
l_1 r_1
l_2 r_2
:
l_N r_N

Output

Print the minimum cost to achieve connectivity.

Sample Input 1

3
1 3
5 7
1 3

Sample Output 1

2

The second rectangle should be moved to the left by a distance of 2.

Sample Input 2

3
2 5
4 6
1 4

Sample Output 2

0

The rectangles are already connected, and thus no move is needed.

Sample Input 3

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

Sample Output 3

1999999680

Sample Input 4

5
123456 789012
123 456
12 345678901
123456 789012
1 23

Sample Output 4

246433

Sample Input 5

1
1 400

Sample Output 5

0