Problem 23662 --棋盘覆盖

23662: 棋盘覆盖

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 32  Solved: 10
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][92kb]

Description

给出一张n*n(n<=100)的国际象棋棋盘,其中被删除了一些点,问可以使用多少1*2的多米诺骨牌进行掩盖。

Input

第一行为n,m(表示有m个删除的格子)
第二行到m+1行为x,y,分别表示删除格子所在的位置
x为第x行
y为第y列

Output

一个数,即最大覆盖格数

Sample Input

8 0

Sample Output

32

HINT

Source

[Submit][Status]