AT_arc219_g.Traveling Door-to-Door Salesman (Stairs)

Note: This problem has almost the same setting as Problem C. 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 stairs. The cost of this move is $\mathbf{1}$.

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.

注意：本题的设定与问题 C 几乎完全相同。题目描述中的差异以红色粗体标出。

有一个由 $H$ 行 $W$ 列网格表示的地下公寓。从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子记为格子 $(i,j)$。

地下公寓的入口位于格子 $(1,1)$。

地下公寓内共有 $N$ 扇门。第 $k$ 扇门位于格子 $(A_k, B_k)$。

在地下公寓内部，一名推销员可以任意次、以任意顺序执行以下两种移动操作：

• 他可以从当前格子向水平相邻的格子（左或右）行走，该操作花费为 $1$。
• 若他当前所在格子位于第 $1$ 列或第 $W$ 列，则他可通过楼梯移动到垂直相邻的格子（上或下），该操作花费为 $\mathbf{1}$。

他的目标是从格子 $(1,1)$ 出发，经过若干次移动，至少访问全部 $N$ 个有门的格子一次，最终返回格子 $(1,1)$。

求达成该目标所需的最小总花费。

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

$H$ $W$
$N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输入从标准输入中按以下格式给出：

$H$ $W$
$N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

Output the answer on a single line.

在单行中输出答案。

Sample 1 Explanation:
By moving as follows, the goal can be achieved with a total cost of $28$:

• Start from cell $(1,1)$.
• Move $1$ cell down and $1$ cell right from cell $(1,1)$ to visit cell $(2,2)$ (cost $2$).
• Move $1$ cell left and $1$ cell down from cell $(2,2)$ to visit cell $(3,1)$ (cost $2$).
• Move $3$ cells down and $2$ cells right from cell $(3,1)$ to visit cell $(6,3)$ (cost $5$).
• 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 $7$).
• Move $1$ cell right, $1$ cell up, and $4$ cells left from cell $(2,7)$ to visit cell $(1,4)$ (cost $6$).
• Move $3$ cells left from cell $(1,4)$ to arrive at cell $(1,1)$ (cost $3$).

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.

样例 1 解释：
通过以下移动方式，可以以总代价 $28$ 实现目标：

• 从单元格 $(1,1)$ 出发。
• 从单元格 $(1,1)$ 向下移动 $1$ 格、向右移动 $1$ 格，到达单元格 $(2,2)$（代价为 $2$）。
• 从单元格 $(2,2)$ 向左移动 $1$ 格、向下移动 $1$ 格，到达单元格 $(3,1)$（代价为 $2$）。
• 从单元格 $(3,1)$ 向下移动 $3$ 格、向右移动 $2$ 格，到达单元格 $(6,3)$（代价为 $5$）。
• 从单元格 $(6,3)$ 向右移动 $1$ 格，到达单元格 $(6,4)$（代价为 $1$）。
• 从单元格 $(6,4)$ 向右移动 $2$ 格，到达单元格 $(6,6)$（代价为 $2$）。
• 从单元格 $(6,6)$ 向右移动 $2$ 格、向上移动 $4$ 格、向左移动 $1$ 格，到达单元格 $(2,7)$（代价为 $7$）。
• 从单元格 $(2,7)$ 向右移动 $1$ 格、向上移动 $1$ 格、向左移动 $4$ 格，到达单元格 $(1,4)$（代价为 $6$）。
• 从单元格 $(1,4)$ 向左移动 $3$ 格，回到单元格 $(1,1)$（代价为 $3$）。

限制条件

• $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)$ 互不相同。
• 所有输入值均为整数。