ACM-ICPC-OJ训练营

问题 H: 切蛋糕(hard)

时间限制: 2 Sec 内存限制: 512 MB
提交: 0 解决: 10
[提交][状态][讨论版][命题人:]

题目描述

本题为easy版本。与hard版本不同的是，两者的数据范围不同。
现在有一块N*N的蛋糕。小h想把蛋糕切开分给朋友们，小h每次会切一块长为2，宽为1的蛋糕。
为了方便理解，你可以将这块蛋糕看作是一个N*N的方格阵。
但是这块蛋糕有些不同，有一些1*1的位置无法被切割。
换句话说，对于最后切出来的蛋糕，不能包含这些无法切割的位置。

他想问你最多能切出来多少块蛋糕，你能帮帮他吗？

输入描述

第一行包含两个整数 N 和 t，其中 t 为无法被切割的位置的数量。(1≤N≤100,0≤t≤min(N*N,100))
接下来 t 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的蛋糕无法被切割。
请注意：行列数从 1 开始。

输出描述

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

样例输入

2 1
1 2

样例输出

提示

样例解释：

对于一个2X2的蛋糕

你可以选择切[1,1]到[2,1]或者[2,1]到[2,2]这样一块2X1的蛋糕。但你不能切出[1,1]到[1,2]或者[2,2]到[1,2]这样的蛋糕，因为[1,2]无法被切割。

所以最终答案为1。

[提交][状态]