Variant Chess: Dabbaba

Interview

Time limit2sMemory limit1024 MB

Summary

Count the distinct empty squares on an N by N board that at least one Dabbaba can reach by moving exactly 2 squares up, down, left, or right.

Level: Easy3 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

Eundong likes playing with chess pieces more than playing chess itself. Today he wants to play with the Dabbaba, one of the variant chess pieces, on a $N \times N$ board.

Dabbaba move

A Dabbaba moves 2 squares up, down, left, or right. Like a knight, it can jump over other pieces. However, it cannot move outside the board, and it cannot move to a square occupied by another piece.

While Eundong was playing, Beusil accidentally scattered Dabbabas across the board. Looking at the board, Eundong thought for a moment and wondered how many squares a Dabbaba on the board can reach in one move.

Given the board size $N$ and the number of Dabbabas $K$ , count all squares that a Dabbaba can reach in one move. If several moves reach the same square, count it only once.

Input

The first line contains the board size $N$ and the number of Dabbabas $K$ , separated by a space. $(1 \le N \le 100\,000;$ $1 \le K \le \min(N^2, 100\,000))$

The second through $(K+1)$ -th lines each contain the position $X, Y$ of a Dabbaba, separated by a space. $(1 \le X, Y \le N)$

No two pieces are on the same square.

Output

Print the number of squares that a Dabbaba on the board can reach in one move.

Examples5

Example 1
Input
```
8 2
2 2
5 5
```
Expected output
```
6
```
Example 2
Input
```
3 2
1 1
3 3
```
Expected output
```
2
```
Example 3
Input
```
3 4
1 1
1 3
3 1
3 3
```
Expected output
```
0
```
Example 4
Input
```
3 4
1 1
1 2
2 1
2 2
```
Expected output
```
4
```

Example 5

Input

Expected output