Problem Description

On an $n \times n$ chessboard there are $n$ pieces. Each time, you may move one piece one step in one of the four directions: up, down, left, or right. In the end, the pieces must form a single row, a single column, or lie on the main diagonal or the anti-diagonal (so there are $2n + 2$ possible target states in total). Find the minimum number of moves.

Some cells on the board are obstacles, and a piece can never pass through them at any time. The initial positions of the pieces are guaranteed not to be on obstacles. No two pieces may end up on the same cell at the same time.

Input Format

The first line contains two integers $n$ and $m$, representing the number of pieces (which is also the side length of the board) and the number of obstacles.

The next $n$ lines each contain two integers $x$ and $y$, representing the coordinates of the $i$-th piece ($1 \le x, y \le n$).

The next $m$ lines each contain the coordinates of an obstacle. It is guaranteed that these $n + m$ coordinates are all distinct.

Output Format

Output a single integer, the minimum number of moves. If there is no solution, output -1.

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

6

Hint

[Sample Explanation]

[Constraints]

For $50\%$ of the testdata, $n \le 15$ and $m = 0$.

For $100\%$ of the testdata, $2 \le n \le 50$ and $0 \le m \le 100$.

Translated by ChatGPT 5