N - パワーアップ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

縦 10^9 マス、横 10^9 マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と呼びます。
はじめ、(1, 1) に主人公がいます。主人公は現在いるマスから上下左右の隣接するマスに移動できます。主人公はマス (A, B) に移動するとパワーアップして、それ以降は現在いるマスから 8 近傍のマスに移動できるようになります。

  • ここで (i, j) の 8 近傍とは (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) にいる。
  • 3 回の移動により (4, 1) にあるコインを拾う。
  • 2 回の移動により (5, 2) に着き、パワーアップする。
  • 1 回の移動により (6, 3) にあるコインを拾う。
  • 5 回の移動により (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

Problem Statement

There is a 10^9 \times 10^9 grid. Let (i, j) denote the cell in the i-th row from the top and j-th column from the left.
The hero is initially at (1, 1). He can move to one of the four adjacent cells: up, down, left, or right. Once he reaches cell (A, B), the hero powers up, after which he can move to one of the eight adjacent cells.

  • The eight cells adjacent to (i, j) are (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) (except for non-existent ones).

Besides, there are N coins. Coin i is at cell (C_i, D_i). He can collect the coin when he reaches the cell.
He wants to collect all the coins. At least how many moves are required to collect them?

Constraints

  • 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) are pairwise distinct.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N A B
C_1 D_1
C_2 D_2
\vdots
C_N D_N

Output

Print the answer.

Sample Input 1

3 5 2
4 1
1 7
6 3

Sample Output 1

11

The hero can make the following 11 moves to collect all the coins.

  • The hero is initially at (1, 1).
  • He makes three moves to collect the coin at (4, 1).
  • He makes two moves to reach (5, 2) and power up.
  • He makes one move to collect the coin at (6, 3).
  • He makes five moves to collect the coin at (1, 7).

Since he cannot collect all the coins with 10 moves or less, the answer is 11.

Sample Input 2

3 500000000 500000000
1 1000000000
1000000000 1
1000000000 1000000000

Sample Output 2

2999999997

Sample Input 3

8 36 49
73 52
38 86
30 52
85 48
27 60
45 40
65 98
71 37

Sample Output 3

228