马克西姆在笛卡尔平面上行走。最初,他站在 $$$(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$$$ 的可能答案之一。