AT_arc219_c [ARC219C] Traveling Door-to-Door Salesman (Elevator)

**注意：本题与问题 G 的设定几乎相同，题目陈述的不同之处以粗体标出。** 有一个由 $H$ 行 $W$ 列组成的地下公寓。第 $i$ 行第 $j$ 列的格子表示为格子 $(i, j)$。 地下公寓的入口在格子 $(1,1)$。 地下公寓内有 $N$ 扇门。第 $k$ 扇门位于格子 $(A_k, B_k)$。 在地下公寓内，推销员可以按照任意顺序、任意多次执行以下两种移动方式： - 他可以从当前格子水平移动到邻近的格子（左或右移动一格），该操作花费 $1$。 - 如果他当前所在的格子在第 $1$ 列或第 $W$ 列，可以**乘电梯**垂直移动到相邻的格子（向上或向下移动一格），该操作的花费是 $\mathbf{0}$。 他的目标是从格子 $(1,1)$ 出发，通过重复上述的移动方式，至少访问所有有门的 $N$ 个格子各一次，最后回到格子 $(1,1)$。 请你求出完成这一目标所需的最小总代价。

输入从标准输入读入，格式如下： > $H$ $W$ $N$ $A_1$ $B_1$ $ \vdots $ $A_N$ $B_N$

输出一行一个整数，表示答案。

### 样例解释 1 可以按以下方式移动，使总代价为 $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$）。 ### 数据范围 - $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)$ 各不相同。 - 所有输入都是整数。 由 ChatGPT 5 翻译