[Baltic2001]Knights

在一个 $N\times N$ 的棋盘上，有些方格不能放置骑士。骑士的攻击方式与中国象棋中的马相同，最多可以攻击周围 $8$ 个位置。

请在所有可用方格中放置尽可能多的骑士，使任意两个骑士都不在彼此的攻击范围内，并求出最多可以放置的骑士数量。

输入格式

第一行包含两个整数 $N,M$，分别表示棋盘的边长和不能放置骑士的方格数量。

接下来 $M$ 行，每行包含两个整数，表示一个不能放置骑士的方格坐标。

输出格式

输出一个整数，表示最多可以放置的骑士数量。

样例输入

3 2
1 1
3 3

样例输出

5

数据范围

• $1\le N\le 200$；
• $0\le M$。

来源与许可

本题为 Baltic OI 2001 试题「Knights」，题面与测试数据整理自 BZOJ 1381。

样例 1

输入

3 2
1 1
3 3

输出

5