题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — II etap Arkanoid

Arkanoid 是一款经典的电脑游戏，玩家通过移动一块挡板，反弹在游戏区域内移动的小球，用以击碎区域中的砖块。目标是击碎所有砖块。熟悉这款游戏的玩家都知道，击碎最后几块砖块往往既耗时又令人抓狂。因此，编写一个程序，根据初始游戏区域布局，计算赢得游戏所需的时间，将大有裨益。为简化问题，我们假设玩家操作完美无瑕，总能用挡板中心精准反弹小球。

游戏区域为长 $m$、高 $n$ 的矩形，其中 $m$ 为奇数，且 $m$ 与 $n$ 互质。区域上定义了一个直角坐标系：左下角为 $(0, 0)$，右上角为 $(m, n)$。为简化模型，假设小球尺寸可忽略，挡板厚度也可忽略。挡板沿直线 $y=0$ 水平移动，小球初始位于点 $\left(\frac{m}{2}, 0\right)$，初始速度向量为 $\left(-\frac{1}{2}, \frac{1}{2}\right)$。

当小球触碰到挡板、区域边界或任意砖块时，会发生完全弹性碰撞。此外，被触碰的砖块将被击碎并从区域中消失。请计算经过多少时间单位，所有砖块被击碎。

输入格式

第一行包含三个整数 $m, n, k$ $(m, n, k \geq 1, k \leq n m - 1)$，分别表示游戏区域的宽度、高度和初始砖块数量。

接下来的 $k$ 行描述砖块位置，第 $i$ 行包含两个整数 $x_i, y_i$ $(1 \leq x_i \leq m, 1 \leq y_i \leq n)$，表示存在一块砖块，其为对角顶点为 $(x_i - 1, y_i - 1)$ 和 $(x_i, y_i)$ 的矩形。保证位置 $(x_i = \frac{m+1}{2}, y_i = 1)$ 处无砖块。

输出格式

输出一行，包含一个整数，表示所有砖块被击碎所需的时间单位数。

5 4 3
2 3
5 2
3 3

22

提示

样例 1 解释

附加样例

1. $m=5, n=4, k=2$，答案较大。
2. $m=11, n=10$，砖块构成不触碰区域边界的棋盘格布局。
3. $m=99999, n=100000$，砖块位于 $\left(\frac{m-1}{2}, 2\right), \left(\frac{m-5}{2}, 2\right), \left(\frac{m-9}{2}, 2\right), \ldots$。
4. $m=99999, n=100000$，仅一块砖块位于 $(1, 1)$，答案较大。

详细子任务附加限制及分值如下表所示。