逐户上门推销员（电梯）

时间限制：2s
空间限制：1024MB

题目描述

有一座由 $H$ 行 $W$ 列组成的地下公寓，从上到下第 $i$ 行、从左到右第 $j$ 列的格子记为 $(i,j)$。公寓入口位于 $(1,1)$，其中有 $N$ 扇门，第 $k$ 扇门位于 $(A_k,B_k)$。

推销员从 $(1,1)$ 出发，可以以任意顺序执行任意多次下列移动：

• 从当前格子水平走到左侧或右侧相邻格子，代价为 $1$；
• 当前位于第 $1$ 列或第 $W$ 列时，可以乘电梯竖直移动到上方或下方相邻格子，代价为 $0$。

他需要访问每一扇门所在的格子至少一次，最后回到 $(1,1)$。求所需的最小总代价。

输入格式

第一行输入两个整数 $H,W$。

第二行输入一个整数 $N$。

接下来 $N$ 行，第 $k$ 行输入两个整数 $A_k,B_k$。

输出格式

输出一个整数，表示最小总代价。

样例输入 1

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

样例输出 1

18

样例输入 2

1000000000 1000000000
2
888888888 600000000
1000000000 700000000

样例输出 2

1999999998

数据范围

对于所有数据：

• $1\le H\le 10^9$；
• $2\le W\le 10^9$；
• $1\le N\le 3\times 10^5$；
• $1\le A_k\le H$，$1\le B_k\le W$；
• 所有 $(A_k,B_k)$ 两两不同。