C - Traveling Door-to-Door Salesman (Elevator) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

注：この問題は G 問題とほとんど同じ設定です。問題文中の相違点を赤い太字で示します。

H 行 W 列のグリッドで表される地下アパートがあります。上から i 行目・左から j 列目のマスをマス (i,j) と表記します。

地下アパートの出入り口はマス (1,1) にあります。

地下アパートにはドアが N 個あります。k 個目のドアはマス (A_k, B_k) にあります。

地下アパート内で、セールスマンは以下の 2 種類の移動を好きな順番で何回でも行えます。

  • 現在いるマスから左か右に隣接するマスに徒歩で移動できる。この移動はコストを 1 消費する。
  • 現在いるマスが 1 列目または W 列目の場合、そこから上か下に隣接するマスにエレベーターで移動できる。この移動はコストを \mathbf{0} 消費する。

セールスマンの目標は、マス (1,1) から出発して移動を繰り返し、ドアのある N 個のマスすべてを 1 回以上訪問してからマス (1,1) に到着することです。

セールスマンが目標を達成するために消費する総コストの最小値を求めてください。

制約

  • 1 \leq H \leq 10^9
  • 2 \leq W \leq 10^9
  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A_k \leq H
  • 1 \leq B_k \leq W
  • (A_1, B_1), \dots, (A_N, B_N) は相異なる
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H W
N
A_1 B_1
\vdots
A_N B_N

出力

答えを 1 行に出力せよ。

入力例 1

6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6

出力例 1

18

以下のように移動することで、総コスト 18 で目標を達成できます。

  • マス (1,1) から出発する。
  • マス (1,1) から下に 1 マス、右に 1 マス移動し、マス (2,2) を訪れる(コスト 1)。
  • マス (2,2) から左に 1 マス、下に 1 マス移動し、マス (3,1) を訪れる(コスト 1)。
  • マス (3,1) から下に 3 マス、右に 2 マス移動し、マス (6,3) を訪れる(コスト 2)。
  • マス (6,3) から右に 1 マス移動し、マス (6,4) を訪れる(コスト 1)。
  • マス (6,4) から右に 2 マス移動し、マス (6,6) を訪れる(コスト 2)。
  • マス (6,6) から右に 2 マス、上に 4 マス、左に 1 マス移動し、マス (2,7) を訪れる(コスト 3)。
  • マス (2,7) から右に 1 マス、上に 1 マス、左に 4 マス移動し、マス (1,4) を訪れる(コスト 5)。
  • マス (1,4) から左に 3 マス移動し、マス (1,1) に到着する(コスト 3)。

入力例 2

1000000000 1000000000
2
888888888 600000000
1000000000 700000000

出力例 2

1999999998

Score : 500 points

Problem Statement

Note: This problem has almost the same setting as Problem G. The differences in the problem statements are shown in red bold.

There is an underground apartment represented by a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j).

The entrance to the underground apartment is at cell (1,1).

The underground apartment has N doors. The k-th door is located at cell (A_k, B_k).

Inside the underground apartment, a salesman can perform the following two types of moves any number of times, in any order:

  • He can walk to a horizontally adjacent cell (left or right) from his current cell. The cost of this move is 1.
  • If his current cell is in column 1 or column W, he can move to a vertically adjacent cell (up or down) by elevator. The cost of this move is \mathbf{0}.

His goal is to start from cell (1,1), repeat moves, visit all N cells with doors at least once, and then arrive at cell (1,1).

Find the minimum total cost needed to achieve his goal.

Constraints

  • 1 \leq H \leq 10^9
  • 2 \leq W \leq 10^9
  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq A_k \leq H
  • 1 \leq B_k \leq W
  • (A_1, B_1), \dots, (A_N, B_N) are distinct.
  • All input values are integers.

Input

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

H W
N
A_1 B_1
\vdots
A_N B_N

Output

Output the answer on a single line.

Sample Input 1

6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6

Sample Output 1

18

By moving as follows, the goal can be achieved with a total cost of 18:

  • Start from cell (1,1).
  • Move 1 cell down and 1 cell right from cell (1,1) to visit cell (2,2) (cost 1).
  • Move 1 cell left and 1 cell down from cell (2,2) to visit cell (3,1) (cost 1).
  • Move 3 cells down and 2 cells right from cell (3,1) to visit cell (6,3) (cost 2).
  • Move 1 cell right from cell (6,3) to visit cell (6,4) (cost 1).
  • Move 2 cells right from cell (6,4) to visit cell (6,6) (cost 2).
  • Move 2 cells right, 4 cells up, and 1 cell left from cell (6,6) to visit cell (2,7) (cost 3).
  • Move 1 cell right, 1 cell up, and 4 cells left from cell (2,7) to visit cell (1,4) (cost 5).
  • Move 3 cells left from cell (1,4) to arrive at cell (1,1) (cost 3).

Sample Input 2

1000000000 1000000000
2
888888888 600000000
1000000000 700000000

Sample Output 2

1999999998