AT_arc219_g [ARC219G] Traveling Door-to-Door Salesman (Stairs)

**注意：本题与 Problem 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)$。 请计算完成该目标所需的最小总花费。

输入按以下格式从标准输入读入： > $H$ $W$ $N$ $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_N$ $B_N$

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

### 样例解释 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)$ 各不相同。 - 所有输入均为整数。 由 ChatGPT 5 翻译