372. 棋盘覆盖

给定一个N行N列的棋盘,已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数N和t,其中t为禁止放置的格子的数量。

接下来t行每行包含两个整数x和y,表示位于第x行第y列的格子禁止放置,行列数从1开始。

输出格式

输出一个整数,表示结果。

数据范围

$1 \le N \le 100$

输出样例:

8 0

输出样例:

32