配点: 100 点
JOI先生的收藏室里有一张非常大的桌子,上面有很多值钱的硬币。为了清理办公桌,JOI 先生决定整理并排列他的硬币。
桌子是 它是一个 2\,000\,000\,001 \times 2\,000\,000\,001 的正方形。从左到右,各列是 -1\,000\,000\,000 减去 1\,000\,000\,000 。 它们的编号最大为 -1\,000\,000\,000 减去 1\,000\,000\,000 。列号是 x,行号是 y ( 让我们将其表示为x, y)。
硬币是 2N 目前可用,i 番目 (1 \leqq i \leqq 2N)硬币是正方形(X_i, Y_i)。 JOI先生的目标是1 \leqq x \leqq N 和 1 \leqq y \leqq 2 满足 (x, y) 每个 2N 方格内放置一枚硬币。 1 要一一放置。为了避免损坏硬币, 1 您只能选择一枚硬币并将其移动到与放置它的方格相邻的方格之一。在此过程中,同一个方格上可能会放置多个硬币。 JOI先生希望通过尽可能少的操作来实现他的目标。
给定硬币数量和硬币当前放置的方格,编写一个程序,找出实现目标所需的最少操作数。
入力
输入是按以下格式从标准输入给出的。
N
X_1 Y_1
\vdots
X_{2N} Y_{2N}
出力
将实现目标所需的最少操作数写入标准输出。 1 请以行的形式输出。
制約
- 1 \leqq N \leqq 100\,000.
- -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N).
- -1\,000\,000\,000 \leqq Y_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq 2N).
小課題
- (8 点) N \leqq 10.
- (29 点) N \leqq 1\,000.
- (63 点)没有额外的限制。
入力例 1
3 0 0 0 4 4 0 2 1 2 5 -1 1
出力例 1
15
在此输入示例中,6 硬币的放置方式如下图所示。目标是在粗体框指示的位置收集硬币。

例如,如果您按如下方式移动硬币, 您只需15 操作即可实现您的目标:
- 1 第枚硬币:( 由于无法通过少于0, 0) → (1, 0) → (1, 1) → (1, 2)
- 2 第枚硬币:( 由于无法通过少于0, 4) → (1, 4) → (1, 3) → (2, 3) → (3, 3) → (3, 2)
- 3 第枚硬币:( 由于无法通过少于4, 0) → (4, 1) → (3, 1)
- 5 第枚硬币:( 由于无法通过少于2, 5) → (2, 4) → (2, 3) → (2, 2)
- 6 第枚硬币:( 由于无法通过少于-1, 1) → (0, 1) → (1, 1)
14 次操作来实现目标, 输出15 。 你只需要砍掉
入力例 2
4 2 1 2 1 2 1 3 1 3 1 3 1 3 1 3 1
出力例 2
9
多个硬币可以放置在同一个方块上。
入力例 3
5 1000000000 1000000000 -1000000000 1000000000 -1000000000 -1000000000 1000000000 -1000000000 -1 -5 -2 2 2 8 4 7 -2 5 7 3
出力例 3
8000000029