Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. A New Beginning

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAnnie 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.

Examples

Input

2 1 1 2 2

Output

0

Input

2 1 1 2 0

Output

1

Input

3 5 5 7 7 4 9

Output

2

Input

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

Output

19

Input

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

Output

6

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/02/2021 17:39:42 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|