Spiral

Kalemegdan Park is the largest park in Belgrade. Model the park as an $N \times N$ grid of $N^2$ unit fields. Some fields contain a fountain; every other field is empty. A rider may move between two empty fields only when they share an edge (up, down, left, or right).

The rider only likes spiral routes. A spiral route is built as follows: choose a starting empty field and a starting direction (North, East, South, or West). Move at least one field in that direction, then turn 90 degrees to the right; move at least one field in the new direction, and turn 90 degrees to the right again; move at least one field, and after a final 90 degree right turn move at least one more field. A route therefore consists of exactly four straight segments, and every turn is clockwise.

The route may never pass through a fountain and may never visit the same field twice. The length of a spiral route is the number of fields it covers (equivalently, one plus the total number of steps taken).

The figure above shows a park with $N = 6$ (black squares are fountains) together with a few possible spiral routes.

Print the length of the longest spiral route the rider can take.

The first line contains two integers $N$ and $K$: the side length of the square park and the number of fountains.

Each of the next $K$ lines contains two integers $x$ and $y$, the coordinates of one fountain. Field $(x, y)$ lies in row $x$ counted from the top and column $y$ counted from the left, so $(1, 1)$ is the top-left field and $(N, 1)$ is the bottom-left field. North means up, East means right, South means down, and West means left.

Print a single integer: the length of the longest spiral route. At least one spiral route is guaranteed to exist.

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