给定一张 N×M 的四连通网格图。有 Q 个人,第 i 个人初始时位于 (Xi,Yi)。你需要给所有人规划一条走到边界(第一行/最后一行/第一列/最后一列)上的路径,且任意两条路径不在网格处相交。
你需要判断是否有解。如果有解,你还需要求出所有人的路径长度之和的最小值。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含三个整数 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≤N,M≤200。
对于 100% 的数据,1≤N,M≤2000,1≤NM≤200000。
注
- 赛时并未提供数据组数,“请选手自行评估”
- 赛时并未提供空间限制,
“请选手自行评估”QOJ 上设置为 1 GB。