~N~ people have gathered to trade their hats! They have numbered themselves from ~1~ to ~N~ and lined up in this order. The ~i^\text{th}~ person initially has a hat with value ~v_i~ but would like a hat with value ~w_i~. After some discussion, the hat fans decided on the following method of hat trading: The first person in line can either leave with the hat currently on their head, or they may switch hats with the person directly behind them (if there is anyone) and then leave. This process happens ~N~ times until everyone has left.

At the end of this process, say person ~i~ left wearing a hat valued at ~h_i~. The overall unhappiness is then defined as ~\sum_{i=1}^N |h_i - w_i|~. Can you help these traders minimize their overall unhappiness?

Constraints

~1 \le v_i, w_i \le 1\,000\,000~

Subtask 1 [20%]

~1 \le N \le 20~

Subtask 2 [30%]

~1 \le N \le 2\,000~

Subtask 3 [50%]

~1 \le N \le 200\,000~

Input Specification

The first line contains a single integer ~N~.
The next ~N~ lines each contain two space-separated integers, ~v_i~ and ~w_i~.

Output Specification

Output a single space-separated integer, the minimum possible unhappiness.

Sample Input

4
15 4
3 18
10 3
8 2

Sample Output

17

Explanation for Sample

The first person trades his hat with the second person in line and leaves with a hat of value ~3~. The next three people leave without any more trades. The overall unhappiness is ~|3-4| + |15-18| + |10-3| + |8-2| = 17~ which is the minimum.