← 返回题目列表

AtCoder · arc219_g

G. 上门推销员(楼梯)

中文机器翻译题面 查看原题

分数: 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