问题陈述
有一个 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)。 当他到达牢房时,他可以收集硬币。
他想收集所有硬币。 至少需要多少步才能收集到?
约束
- 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) 成对不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A B C_1 D_1 C_2 D_2 \vdots C_N D_N
输出
打印答案。
示例输入 1
3 5 2 4 1 1 7 6 3
示例输出 1
11
英雄可以做出以下动作 11 移动以收集所有硬币。
- 英雄最初位于 (1, 1).
- 他做了三步来收集硬币 (4, 1).
- 他做了两步到达 (5, 2) 并通电。
- 他采取了一个动作来收集硬币 (6, 3).
- 他做了五步来收集硬币 (1, 7).
因为他无法收集所有硬币 10 移动或更少,答案是 11.
示例输入 2
3 500000000 500000000 1 1000000000 1000000000 1 1000000000 1000000000
示例输出 2
2999999997
示例输入 3
8 36 49 73 52 38 86 30 52 85 48 27 60 45 40 65 98 71 37
示例输出 3
228