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 potatoes to plant, and the -th potato must be planted at . Starting at the point , Bob begins walking, in one step he can travel one unit right or up (increasing his or coordinate by respectively). At any point during his walk, he can plant some potatoes at arbitrary points using his potato gun, consuming units of energy in order to plant a potato at . 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 .
The next lines contain two integers and , representing the location of the -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 of the score, .
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 , Bob plants the second potato using energy. Next, he travels to and plants the first potato with energy.
Sample Input 3
3
5 5
7 7
4 9
Sample Output 3
2
Explanation 3
Moving to , Bob plants the first potato using energy. Next, he travels to and plants the third potato with energy. Finally, he travels to and plants the second potato with 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
Comments