Arkanoid 是一款电脑游戏，玩家通过移动挡板（球拍）来反弹小球。游戏的目标是消除场地内的所有砖块，每当小球击中砖块时，砖块就会被消除（同时小球反弹）。所有玩过这个游戏的人都知道，击中最后剩下的几块砖是多么令人沮丧且耗时。因此，如果能有一个程序，针对给定的初始场地配置，计算出赢得游戏所需的时间，将会非常方便。为了本题的目的，我们假设玩家操作完美，即总是用挡板的中点反弹小球。
游戏场地宽为 $m$，高为 $n$，其中 $m$ 为奇数，且 $m$ 与 $n$ 互质*。我们在场地上建立笛卡尔坐标系，使得左下角坐标为 $(0, 0)$，右上角坐标为 $(m, n)$。为简化起见，我们假设小球的大小和挡板的厚度均可忽略不计。挡板沿直线 $y = 0$ 移动，小球的初始位置为 $(\frac{m}{2}, 0)$，其初始速度（向量）为 $(-\frac{1}{2}, \frac{1}{2})$。
当小球击中挡板、场地边缘或任何砖块时，会发生弹性碰撞并反弹。然而，任何被击中的砖块都会碎裂并立即从场地中移除。请问直到所有砖块都被移除需要多少时间单位？
输入格式
标准输入的第一行包含三个整数 $m, n$ 和 $k$ ($m, n, k \ge 1, k \le nm-1$)，由空格分隔，分别指定了游戏场地的尺寸和初始砖块数量。接下来的 $k$ 行描述了砖块：第 $i$ 行包含一对整数 $x_i$ 和 $y_i$ ($1 \le x_i \le m, 1 \le y_i \le n$)，由空格分隔，表示场地中存在一个正方形砖块，其对角顶点位于 $(x_i - 1, y_i - 1)$ 和 $(x_i, y_i)$。你可以假设在对应于 $x_i = \frac{m+1}{2}, y_i = 1$ 的正方形区域内没有砖块。
输出格式
在标准输出的唯一一行中，打印一个整数，表示直到所有砖块被移除所需的时间单位数。
样例
输入格式 1
5 4 3 2 3 5 2 3 3
输出格式 1
22
样例评分测试
- 1ocen: $m = 5, n = 4, k = 2$，结果较大。
- 2ocen: $m = 11, n = 10$，砖块形成棋盘状，且不接触场地边缘。
- 3ocen: $m = 99\,999, n = 100\,000$，砖块位于位置 $(\frac{m-1}{2}, 2), (\frac{m-5}{2}, 2), (\frac{m-9}{2}, 2), \dots$。
- 4ocen: $m = 99\,999, n = 100\,000$，在 $(1, 1)$ 处有一个砖块，结果较大。
子任务
测试集由以下具有特定属性的子集组成。每个子集内可能包含多个测试组。
| 子任务 | 属性 | 分值 |
|---|---|---|
| 1 | $m, n \le 100, k \le 1000$ | 25 |
| 2 | $n, m \le 100\,000, k \le 50$ | 25 |
| 3 | $m, n, k \le 100\,000$，且没有砖块与另一块砖或场地边缘共享边（注意砖块可以共享角） | 25 |
| 4 | $m, n, k \le 100\,000$ | 25 |
* 若两个正整数的最大公约数为 1，则称它们互质。