Bob has gotten bored of winning contests and farming rating. Today, he is going to farm potatoes instead.

Bob's garden is an infinite 2D plane. He has ~n~ potatoes to plant, and the ~i~-th potato must be planted at ~(x_i, y_i)~. Starting at the point ~(0, 0)~, Bob begins walking, in one step he can travel one unit right or up (increasing his ~x~ or ~y~ coordinate by ~1~ respectively). At any point ~(X, Y)~ during his walk, he can plant some potatoes at arbitrary points using his potato gun, consuming ~\max(|X-x|, |Y-y|)~ units of energy in order to plant a potato at ~(x, y)~. Find the minimum total energy required to plant every potato.

Note that Bob may plant any number of potatoes from any point.

Input Specification

The first line contains the integer ~n~ ~(1 \le n \le 800\,000)~.

The next ~n~ lines contain two integers ~x_i~ and ~y_i~ ~(0 \le x_i, y_i \le 10^9)~, representing the location of the ~i~-th potato. It is possible that some potatoes should be planted in the same location.

Output Specification

Print the minimum total energy to plant all potatoes.

Subtasks

For ~50\%~ of the score, ~x_i, y_i, n \le 2000~.

Sample Input 1

2
1 1
2 2

Sample Output 1

0

Explanation 1

Bob can travel to each spot directly and plant a potato with no energy required.

Sample Input 2

2
1 1
2 0

Sample Output 2

1

Explanation 2

Moving to ~(1, 0)~, Bob plants the second potato using ~1~ energy. Next, he travels to ~(1, 1)~ and plants the first potato with ~0~ energy.

Sample Input 3

3
5 5
7 7
4 9

Sample Output 3

2

Explanation 3

Moving to ~(5, 5)~, Bob plants the first potato using ~0~ energy. Next, he travels to ~(6, 7)~ and plants the third potato with ~2~ energy. Finally, he travels to ~(7, 7)~ and plants the second potato with ~0~ energy.

Sample Input 4

3
5 5
7 7
4 9

Sample Output 4

2

Sample Input 5

10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5

Sample Output 5

19

Sample Input 6

10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1

Sample Output 6

6