描述

给定一个N行N列的棋盘,已知某些格子禁止放置。求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。N≤100。

输入格式

第一行为n,t(表示有t个删除的格子)
第二行到t+1行为x,y,分别表示删除格子所在的位置
x为第x行,y为第y列,行列编号从1开始。 

输出格式

一个数,即最多能放的骨牌数

样例输入

8 0

样例输出

32