← 返回题目列表

AtCoder · past20_n

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)。 当他到达牢房时,他可以收集硬币。
他想收集所有硬币。 至少需要多少步才能收集到?

约束

  • 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