A New Beginning

题意翻译

你在一个二维平面直角坐标系的原点 $(0,0)$ 上，你可以向上或向右移动 $1$ 单位长度任意次。 现在给你 $n$ 个点，第 $i$ 个点为 $(x_i,y_i)$。你需要对这 $n$ 个点都打上标记。具体的，在任意时刻，如果你在点 $(X,Y)$ 并希望对点 $(x,y)$ 打标记，你需要花费 $\max(|X-x|,|Y-y|)$ 单位能量。 求最少花费多少单位能量。 $1\leq n\leq8\times10^5;0\leq x_i,y_i\leq10^9;$

题目描述

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.

输入输出样例

输入样例 #1

2
1 1
2 2

输出样例 #1

0

输入样例 #2

2
1 1
2 0

输出样例 #2

1

输入样例 #3

3
5 5
7 7
4 9

输出样例 #3

2

输入样例 #4

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

输出样例 #4

19

输入样例 #5

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

输出样例 #5

6

说明

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.

题意翻译

你在一个二维平面直角坐标系的原点 $(0,0)$ 上，你可以向上或向右移动 $1$ 单位长度任意次。 现在给你 $n$ 个点，第 $i$ 个点为 $(x_i,y_i)$。你需要对这 $n$ 个点都打上标记。具体的，在任意时刻，如果你在点 $(X,Y)$ 并希望对点 $(x,y)$ 打标记，你需要花费 $\max(|X-x|,|Y-y|)$ 单位能量。 求最少花费多少单位能量。 $1\leq n\leq8\times10^5;0\leq x_i,y_i\leq10^9;$