A14306 | A New Beginning

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.

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.

Print the minimum total energy to plant all potatoes.