题目描述

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

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

输入格式

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

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

输出格式

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

样例

8 0

32

数据范围

$1≤N≤100,0≤t≤100$

来源

• 算法竞赛进阶指南