← 返回题目列表

Codeforces · 1066/F

F. 又一个二维行走

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

马克西姆在笛卡尔平面上行走。最初,他站在 $$$(0, 0)$$$ 点,一步就能到达四个相邻点(左、右、上、下)中的任意一个。例如,如果 Maksim 当前位于 $$$(0, 0)$$$ 点,他可以一步移动到以下任意点:

- $$$(1, 0)$$$;
- $$$(0, 1)$$$;
- $$$(-1, 0)$$$;
- $$$(0, -1)$$$.

在这个平面上还有 $$$n$$$ 不同的关键点。第 $$$i$$$ 个点是 $$$p_i = (x_i, y_i)$$$。保证$$$0 \le x_i$$$ 和$$$0 \le y_i$$$ 并且没有关键点$$$(0, 0)$$$。

令第一级点为 $$$max(x_i, y_i) = 1$$$ 的点,第二级点为 $$$max(x_i, y_i) = 2$$$ 的点,依此类推。马克西姆想要参观所有的关键点。但如果他没有访问级别 $$$i$$$ 的所有点,他就不应该访问级别 $$$i + 1$$$ 的点。他从给定集合中最低级别的点开始访问这些点。

两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的距离为 $$$|x_1 - x_2| + |y_1 - y_2|$$$ 其中 $$$|v|$$$ 是 $$$v$$$ 的绝对值。

Maksim 希望以尽可能最小的方式访问所有关键点。你的任务是找到这个距离。

如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 关键点的数量。

接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$, $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) — $$$x$$$-关键点的坐标 $$$p_i$$$ 和 $$$y$$$-关键点的坐标$$$p_i$$$。保证所有点都是不同的,并且点 $$$(0, 0)$$$ 不在这个集合中。

输出

打印一个整数——如果马克西姆需要以上述方式访问所有关键点,他必须行驶的最小可能总距离。

示例

输入 #1

8
2 2
1 4
2 3
3 1
3 4
1 1
4 3
1 2

输出 #1

15

输入 #2

5
2 1
1 0
2 0
3 2
0 3

输出 #2

9

注意

第一个例子对应的图片:

长度为 $$$15$$$ 的可能答案之一。

第二个例子对应的图片:

长度为 $$$9$$$ 的可能答案之一。