AT_joi2019ho_d.コイン集め (Coin Collecting)

在 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 \leq i \leq 2N$) 位于位置 $(X_i, Y_i)$。JOI 氏的目标是将这些硬币放到网格左上角的一个小方块中，每个格子恰好放一个。这个小方块由 $(x, y)$ 表示，其中 $1 \leq x \leq N$ 且 $1 \leq y \leq 2$。

为了避免损坏硬币，仅能进行以下操作：选择一枚硬币，并将它移动到与其当前所在位置相邻的另一个格子（即共享一条边的格子）。移动过程中，可以暂时将多个硬币堆叠在一起。JOI 氏希望用尽量少的操作次数实现目标。

现在，给出硬币的数量和它们的初始位置，请编写一个程序，计算用最少多少次操作可以将硬币移到目标位置。

从标准输入中读取数据，格式如下：

$N$ $X_1$ $Y_1$ $\vdots$ $X_{2N}$ $Y_{2N}$

输出一行，表示达成目标位置所需的最小操作次数。

• 条件限制：

  • $1 \leq N \leq 100\,000$。
  • $-1\,000\,000\,000 \leq X_i \leq 1\,000\,000\,000$ ($1 \leq i \leq 2N$)。
  • $-1\,000\,000\,000 \leq Y_i \leq 1\,000\,000\,000$ ($1 \leq i \leq 2N$)。

• 子任务：

  1. （8 分）$N \leq 10$。
  2. （29 分）$N \leq 1\,000$。
  3. （63 分）没有其他额外的约束条件。

示例说明 1

在这个例子中，6 枚硬币的初始位置如下图所示：

我们的目标是将硬币移到粗框标记的区域。例如，通过以下路径移动硬币，可以在 15 次操作后实现目标：

• 第 1 枚硬币：$(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (1, 2)$
• 第 2 枚硬币：$(0, 4) \rightarrow (1, 4) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 2)$
• 第 3 枚硬币：$(4, 0) \rightarrow (4, 1) \rightarrow (3, 1)$
• 第 5 枚硬币：$(2, 5) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (2, 2)$
• 第 6 枚硬币：$(-1, 1) \rightarrow (0, 1) \rightarrow (1, 1)$

无法在 14 次或更少的操作内达成目标，因此输出为 15。

示例说明 2

注意，移动过程中可能会有多个硬币暂时放在同一个格子中。

本翻译由 AI 自动生成