骑士共存问题

题目描述

在一个 n\*n个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入 ![](https://cdn.luogu.org/upload/pic/2669.png) 对于给定的 n\*n 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击

输入输出格式

输入格式


第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m

输出格式


将计算出的共存骑士数输出

输入输出样例

输入样例 #1

3 2
1 1
3 3

输出样例 #1

5