29721번 - 변형 체스 놀이 : 다바바(Dabbaba)

문제

은동이는 체스를 두는 것보다 체스 기물을 가지고 노는 것을 좋아한다. 오늘은 변형 체스 기물 중 하나인 다바바(Dabbaba)를 가지고 크기가 $N \times N$인 체스판 위에서 놀아보려고 한다.

다바바의 행마

다바바는 상하좌우 중 하나로 2ドル$칸을 이동하며 나이트처럼 다른 기물을 뛰어넘을 수 있는 변형 체스 기물이다. 단, 체스판 밖으로 이동하려 하거나 이동하려는 칸에 다른 기물이 있으면 이동하지 못한다.

체스 기물을 가지고 놀던 중 브실이가 실수로 체스판 위에 다바바를 흩뿌려 버렸다. 흩뿌려진 체스판을 본 은동이는 잠시 생각하다가 현재 체스판 위에 있는 다바바가 한 번 이동하여 도착할 수 있는 칸이 총 몇 칸인지 궁금해졌다.

체스판의 크기 $N$과 다바바의 개수 $K$가 주어졌을 때 다바바가 한 번 이동하여 도착할 수 있는 모든 칸의 개수를 구해보자. 동일한 칸에 가는 방법이 여러 가지라도 칸의 개수는 하나로 센다.

입력

첫 번째 줄에 체스판의 크기 $N$과 다바바의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 100,000円;$ 1ドル \le K \le \min(N^2, 100,000円))$

두 번째 줄부터 $K+1$번째 줄까지 다바바의 위치 $X, Y$가 공백으로 구분되어 주어진다. $(1 \le X, Y \le N)$

같은 위치에 2ドル$개 이상의 기물이 존재하지 않는다.

출력

다바바가 한 번 이동하여 도착할 수 있는 모든 칸의 개수를 출력한다.

제한

힌트