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.

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.