问题描述

在一个n*n的棋盘上有n枚棋子。每次可以把一枚棋子往上、下、左、右方向之一移动一格，最后排成一行、一列或者主、副对角线上（因此一共有2n+2条可能的目标状态），要求移动次数最小。

棋盘上有一些位置是障碍，棋子在任何时候都不能经过。棋子的初始位置保证不在障碍物上。任两枚棋子不能在同时到达同一个格子。

【输入文件】

输入文件move.in第一行包含两个整数n, m，表示棋子的个数（它也是棋盘的边长）和障碍的个数。

以下n行，每行两个整数(x, y)，表示第i个棋子的坐标（1<=x, y<=n），以下m行，每行给出一个障碍物的坐标。假设这n+m个坐标两两不重合。

【输出文件】

输出文件仅包含一个整数，表示最小移动步数。如果无解，输出-1。

【输入样例】move.in

5 1
1 2
2 4
3 4
5 1
5 3
1 1

【输出样例】move.out

6

【限制】

50%的数据满足：2<=n<=15，m=0

100%的数据满足：2<=n<=50, 0<=m<=100