给定一张 $N \times M$ 的四连通网格图。有 $Q$ 个人，第 $i$ 个人初始时位于 $(X_i, Y_i)$。你需要给所有人规划一条走到边界（第一行/最后一行/第一列/最后一列）上的路径，且任意两条路径不在网格处相交。

你需要判断是否有解。如果有解，你还需要求出所有人的路径长度之和的最小值。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含三个整数 $N, M, Q$。

接下来 $Q$ 行，每行两个整数 $X, Y$，描述每个点的坐标。

输出格式

对于每组数据：

• 如果不存在合法方案，输出 -1。
• 否则，输出一行一个整数，表示所有人的路径长度之和的最小值。

样例数据

样例输入

4 4 2
2 3
3 3
5 5 3
2 3
2 4
3 2
6 6 5
2 3
3 2
3 3
3 4
4 3

样例输出

2
3
-1

子任务

对于 $70\%$ 的数据，$1 \leq N,M \leq 200$。

对于 $100\%$ 的数据，$1 \leq N,M \leq 2\,000$，$1 \leq NM \leq 20\,0000$。

注

1. 赛时并未提供数据组数，“请选手自行评估”
2. 赛时并未提供空间限制，“请选手自行评估” QOJ 上设置为 1 GB。