AT_past20_n.パワーアップ

有一个 $10^9 \times 10^9$ 的网格。用 $(i, j)$ 表示第 $i$ 行（自上而下）第 $j$ 列（自左向右）的格子。
英雄初始位于 $(1, 1)$。他可以向上、下、左、右四个相邻格子移动之一。当他到达 $(A, B)$ 这个格子后，英雄会“能力提升”，此后可以向八个相邻格子中的任意一个移动。

• $(i, j)$ 的八个相邻格子为 $(i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)$（只包括实际存在的格子）。

此外，网格上有 $N$ 枚硬币。第 $i$ 枚硬币位于 $(C_i, D_i)$。当英雄到达该格子时可以收集一枚硬币。
他想收集所有硬币。请问至少需要多少步才能收集完所有硬币？

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

$N\ A\ B\ C_1\ D_1\ C_2\ D_2\ \cdots\ C_N\ D_N$

输出答案。

样例解释 1

英雄可以通过下述 $11$ 步收集所有硬币。

• 英雄初始在 $(1, 1)$。
• 他用三步到达 $(4, 1)$ 并收集一枚硬币。
• 再用两步移动到 $(5, 2)$ 并获得能力提升。
• 用一步到达 $(6, 3)$ 收集一枚硬币。
• 再用五步到达 $(1, 7)$ 收集最后一枚硬币。

因为在 $10$ 步或更少的步数内无法收集所有硬币，所以答案是 $11$。

数据范围

• $1 \leq N \leq 16$
• $1 \leq A, B, C_i, D_i \leq 10^9$
• $(1, 1), (A, B), (C_1, D_1), \dots, (C_N, D_N)$ 两两不同。
• 所有输入均为整数。

由 ChatGPT 5 翻译