Bob's Farm

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 5.0s
Memory limit: 250M

Problem types

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

Comments

There are no comments at the moment.