P15199 [SWERC 2018] Monument Tour

:::align{center}  ::: 一家旅游运营商提供巴黎 $N$ 个纪念碑和博物馆的参观行程，这些地点被建模为一个网格。旅游的运营方式如下：巴士从西边进入城市（沿任意一条街道），穿越城市，在需要时左转或右转以参观纪念碑，然后返回到它进入城市时所使用的同一条东西向道路，如此重复，直至从东边离开城市。 在一个 $6 \times 5$ 网格城市中的一次旅游可能如上图所示。在图中，巴士从坐标 $(0, 2)$ 进入城市（我们认为 $(0, 0)$ 是城市的西北角），首先参观位于 $(1, 2)$ 的纪念碑（已在主路上），左转参观位于 $(1, 0)$ 的纪念碑，返回主路并向东移动，右转参观位于 $(2, 4)$ 的纪念碑，返回主路，参观位于 $(4, 2)$ 的纪念碑（再次在主路上），然后从坐标 $(5, 2)$ 离开城市。 巴士运营商计算得出，每行驶一个街区的油耗为 1 单位。对于上述例子，成本因此为 $5 + 2 \times 2 + 2 \times 2 = 13$ 单位油耗。 你的任务是帮助旅游运营商选择巴士应该行驶哪条东西向道路，以便在参观所有 $N$ 个纪念碑的同时，使旅游成本最小化。 #### 重要说明 - 巴士运营商不允许返回到另一条平行的东西向道路；他们必须使用与进入城市时相同的道路。 - 同一坐标上可以有多个纪念碑。

输入包含若干行，每行由空格分隔的整数组成： - 第一行包含两个整数 $X$ 和 $Y$，分别表示南北向街道的数量和东西向街道的数量。 - 第二行包含一个整数 $N$，表示旅游需要参观的纪念碑数量。 - 接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示每个纪念碑的坐标。

输出应包含一行，内容为一个整数，表示旅游的最小成本。

#### 数据范围 - $1 \leq X, Y \leq 100\,000$； - $1 \leq N \leq 100\,000$； - $0 \leq x_i < X$，$0 \leq y_i < Y$。 翻译由 DeepSeek 完成