Minimizing Moves to Line Up Pieces on a Chessboard

You are given an n × n chessboard with n pieces placed at distinct locations that are not obstacles. Some cells on the board are obstacles that cannot be passed by any piece. In each move, you may move one piece by one cell in one of the four cardinal directions (up, down, left, right), but a piece cannot move into or pass through an obstacle. Additionally, no two pieces may be in the same cell at the same time.

Your goal is to move the pieces (using a sequence of moves) so that they finally lie along one of the following 2n+2 target configurations:

• All pieces on a single row (any row).
• All pieces on a single column (any column).
• All pieces on the main diagonal, i.e. positions \( (1,1), (2,2), \dots, (n,n) \).
• All pieces on the anti-diagonal, i.e. positions \( (1,n), (2,n-1), \dots, (n,1) \).

Determine the minimum total number of moves required to achieve one of these target configurations. If it is impossible to achieve any target configuration, output -1.

Note: The pieces are moved one by one. Although they may use intermediate positions that have been occupied earlier by another piece (provided that no two pieces are ever simultaneously in the same cell), in the final configuration all pieces must occupy distinct cells in one of the allowed patterns.

inputFormat

The input begins with a line containing two integers n and k (1 ≤ n ≤ 50, 0 ≤ k < n*n) — the size of the board and the number of obstacles.

The next k lines each contain two integers r and c (1-indexed) representing the row and column of an obstacle.

The following n lines each contain two integers r and c (1-indexed) representing the initial position of a piece. It is guaranteed that no piece starts on an obstacle and that all starting positions are distinct.

outputFormat

Output a single integer — the minimum total number of moves required to move all pieces to form one of the allowed target configurations. If it is impossible, output -1.

sample

3 0
1 1
1 3
3 2

2