← 返回题目列表

Codeforces · 1534/G

G. 一个新的开始

中文机器翻译题面 查看原题

安妮已经厌倦了赢得每场编码比赛和耕作无限评级。今天,她要去种土豆。

安妮的花园是一个无限的二维平面。她有 $$$n$$$ 个土豆要种植,第 $$$i$$$ 个土豆必须种植在 $$$(x_i,y_i)$$$。从点 $$$(0, 0)$$$ 开始,安妮开始行走,一步中她可以向右或向上移动一个单位(将 $$$x$$$ 或 $$$y$$$ 坐标分别增加 $$$1$$$)。在行走过程中的任何时刻 $$$(X,Y)$$$,她都可以使用土豆枪在任意点种植一些土豆,消耗 $$$\max(|X-x|,|Y-y|)$$$ 单位的能量,以便在 $$$(x,y)$$$ 处种植土豆。求种植每个马铃薯所需的最低总能量。

请注意,安妮可以从任意地点种植任意数量的土豆。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 800\,000$$$)。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i,y_i \le 10^9$$$),代表第 $$$i$$$ 个马铃薯的位置。可能应该在同一地点种植一些土豆。

输出

打印种植所有土豆的最低总能量。

示例

输入 #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

注意

在$$$1$$$示例中,安妮可以直接前往每个地点并种植土豆,无需任何能量。

在示例 $$$2$$$ 中,移动到 $$$(1,0)$$$,安妮使用 $$$1$$$ 能量种植第二个土豆。接下来,她前往 $$$(1,1)$$$ 并用 $$$0$$$ 能量种植第一个土豆。