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.