Background

On a whim, you go to the park to ride a bike.

Problem Description

The park can be viewed as an $N \times N$ grid. The cell in row $i$ and column $j$ has coordinates $(i,j)$. Each cell is either a passable road or an impassable fountain.

You want to ride along a spiral path.

• A spiral path is defined as: starting from a cell, move in one direction for at least $1$ cell, make a right turn, then move for at least $1$ cell, make a right turn, then move for at least $1$ cell, make a right turn, and then move for at least $1$ cell (turn right exactly three times).
• A spiral path must not pass through any fountain.

Now you want to find the longest spiral path you can ride (the path length is the number of visited cells, including the start and end cells).

It is guaranteed that at least one spiral path exists.

A spiral path must not visit the same cell more than once.

Input Format

The first line contains two integers $N$ and $K$, representing the size of the park and the number of fountains.

The next $K$ lines each contain two integers $x$ and $y$, indicating that there is a fountain at coordinates $(x,y)$.

Output Format

Output one integer: the longest route you can ride (i.e., the longest spiral path).

6 9
2 1
2 4
4 4
6 2
6 3
5 3
4 6
5 1
2 6

14

Hint

Constraints:

Subtask#0 is the sample.

$2\le N\le 1000$, $0\le K\le \min(2000,N^2)$, $1\le x,y\le N$.

Sample Explanation:

The park is shown in the figure. The rightmost picture shows the longest spiral path, whose length is $14$, and there is no longer path.

Note: The first two pictures both show valid spiral paths to help understanding.

Translated by ChatGPT 5