나선

칼레메그단(Kalemegdan) 공원은 베오그라드에서 가장 큰 공원이다. 이 공원을 $N \times N$ 격자, 즉 $N^2$개의 칸으로 생각하자. 어떤 칸에는 분수가 있고, 나머지 칸은 모두 빈 칸이다. 라이더는 변을 공유하는(상·하·좌·우로 인접한) 두 빈 칸 사이에서만 이동할 수 있다.

라이더는 나선 경로만 좋아한다. 나선 경로는 다음과 같이 만든다. 먼저 출발할 빈 칸과 시작 방향(북·동·남·서 중 하나)을 고른다. 그 방향으로 한 칸 이상 이동한 뒤 오른쪽으로 90도 회전하고, 새 방향으로 한 칸 이상 이동한 뒤 다시 오른쪽으로 90도 회전하고, 또 한 칸 이상 이동한 뒤 마지막으로 한 번 더 오른쪽으로 90도 회전하여 다시 한 칸 이상 이동한다. 따라서 경로는 정확히 네 개의 직선 구간으로 이루어지며, 모든 회전은 시계 방향이다.

경로는 분수가 있는 칸을 지날 수 없고, 같은 칸을 두 번 방문할 수도 없다. 나선 경로의 길이는 그 경로가 지나는 칸의 개수이다(즉, 이동한 총 걸음 수에 1을 더한 값과 같다).

위 그림은 $N = 6$인 공원(검은 칸이 분수)과 가능한 몇 가지 나선 경로를 보여 준다.

라이더가 갈 수 있는 가장 긴 나선 경로의 길이를 출력하여라.

첫째 줄에 두 정수 $N$과 $K$가 주어진다. 각각 정사각형 공원의 한 변의 길이와 분수의 개수이다.

이어지는 $K$개의 줄에는 각각 분수 하나의 좌표를 나타내는 두 정수 $x$, $y$가 주어진다. 칸 $(x, y)$는 위에서부터 $x$번째 행, 왼쪽에서부터 $y$번째 열에 있다. 따라서 $(1, 1)$은 왼쪽 위 칸이고 $(N, 1)$은 왼쪽 아래 칸이다. 북쪽은 위, 동쪽은 오른쪽, 남쪽은 아래, 서쪽은 왼쪽을 뜻한다.

가장 긴 나선 경로의 길이를 정수 하나로 출력하여라. 나선 경로는 적어도 하나 존재함이 보장된다.

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