A New Beginning

5000ms

262144K

Description:

Annie has gotten bored of winning every coding contest and farming unlimited rating. Today, she is going to farm potatoes instead.

Annie's garden is an infinite 2D plane. She has $$$n$$$ potatoes to plant, and the $$$i$$$-th potato must be planted at $$$(x_i,y_i)$$$. Starting at the point $$$(0, 0)$$$, Annie begins walking, in one step she can travel one unit right or up (increasing her $$$x$$$ or $$$y$$$ coordinate by $$$1$$$ respectively). At any point $$$(X,Y)$$$ during her walk she can plant some potatoes at arbitrary points using her 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 Annie may plant any number of potatoes from any point.

Input:

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:

Print the minimum total energy to plant all potatoes.

Sample Input:

2
1 1
2 2

Sample Output:

Sample Input:

2
1 1
2 0

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

In example $$$1$$$, Annie can travel to each spot directly and plant a potato with no energy required.

In example $$$2$$$, moving to $$$(1,0)$$$, Annie plants the second potato using $$$1$$$ energy. Next, she travels to $$$(1,1)$$$ and plants the first potato with $$$0$$$ energy.

Informação

Provedor Codeforces

Código CF1534G