题目描述

在一个 $n\times n$ 的棋盘上，有些小方格不能放骑士。

请输出最多可以放多少个骑士，让他们不会攻击到任意其他骑士。

骑士攻击的点如中国象棋中的马，可以攻击 $8$ 个点，没有「别马脚」的规则。

输入格式

第一行给出 $n,m$ 代表棋盘的大小及故障点的个数。

下面 $m$ 行，给出故障点的坐标 $(x_i,y_i)$ 。

输出格式

一行一个整数，表示最多可以放多少个骑士。

3 2
1 1
3 3

5

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq200$，$0\leq m\leq n\times n$。