该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

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

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

输出格式

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

样例

输入样例

8 0

输出样例

32

提示

$\red {1≤N≤100}$