分数: 700 点
问题陈述
注意:该问题与问题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).
找出实现目标所需的最小总成本。
约束
- 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
6 8 7 1 4 2 2 2 7 3 1 6 3 6 4 6 6
示例输出 1
28
通过如下移动,可以实现目标,总成本为 28:
- 从单元格开始 (1,1).
- 移动 1 细胞向下和 1 单元格右侧的单元格 (1,1) 访问单元格 (2,2) (成本 2).
- 移动 1 单元格左侧和 1 单元格从单元格向下 (2,2) 访问单元格 (3,1) (成本 2).
- 移动 3 细胞下降并且 2 单元格右侧的单元格 (3,1) 访问单元格 (6,3) (成本 5).
- 移动 1 单元格右侧的单元格 (6,3) 访问单元格 (6,4) (成本 1).
- 移动 2 单元格右侧的单元格 (6,4) 访问单元格 (6,6) (成本 2).
- 移动 2 单元格右侧, 4 单元格向上,并且 1 单元格左侧的单元格 (6,6) 访问单元格 (2,7) (成本 7).
- 移动 1 单元格右侧, 1 细胞向上,并且 4 单元格左侧的单元格 (2,7) 访问单元格 (1,4) (成本 6).
- 移动 3 单元格左侧的单元格 (1,4) 到达小区 (1,1) (成本 3).
示例输入 2
1000000000 1000000000 2 888888888 600000000 1000000000 700000000
示例输出 2
3999999996