题目描述

在一个 $N \times N$ 的方格棋盘上，有 $t$ 个格子被标记为不可用。你需要放置尽可能多的 $1 \times 2$（或 $2 \times 1$）的矩形骨牌，每块骨牌恰好覆盖两个相邻（上下或左右相邻）的可用格子，且任意两块骨牌不能重叠。求最多能放置多少块骨牌。

输入格式

第一行包含两个整数 $N$ 和 $t$，分别表示棋盘大小和不可用格子的数量。

接下来 $t$ 行，每行两个整数 $x$ 和 $y$（$1 \le x, y \le N$），表示第 $x$ 行第 $y$ 列的格子不可用。行列编号均从 $1$ 开始。

输出格式

输出一个整数，表示最多能放置的骨牌数量。

样例

8 0

32

提示

$1 \le N \le 100$，$0 \le t \le 100$