Description

The town can be viewed as an $n \times n$ grid, where $k$ cells are houses.
There are also lamps in the town. Between every two adjacent cells, there is a lamp.

If two houses are adjacent, then the lamp between these two houses will be lit.
Please find how many lamps are lit in total in this town.

Note: in this problem, “adjacent” means sharing a common edge.

Input Format

The first line contains two integers $n, k$, representing the side length of the grid and the number of houses.
The next $k$ lines each contain two integers $x, y$, representing the coordinates of a house.

Output Format

One line with one integer, representing the answer.

6 12
1 1
2 1
2 2
1 4
3 3
4 3
4 4
3 4
3 6
4 6
5 6
6 6

9

Hint

Sample Explanation

As shown in the figure, the shaded cells are houses, and the red edges are lamps.

Constraints

For $30\%$ of the testdata, $1 \leq n, k \leq 100$.
For $80\%$ of the testdata, $1 \leq n, k \leq 5000$.
For $100\%$ of the testdata, $1 \le n, k \le 10^5$.

Translated by ChatGPT 5