问题描述

有一个纸板，可以看成一个 N×N 的网格图，其中有 K 个格子是坏格子。

现在要从纸板上剪下若干个 1×2 的小矩形。小矩形不能包含坏格子。

问：最多能剪下多少个 1×2 的小矩形？

输入格式

第一行：N, K

接下来 K 行：每行两个整数 i, j，表示第 i 行第 j 列的格子是坏格子。

输出格式

一个整数，表示答案。

输入样例

2 0

输出样例

2

数据范围

1 ≤ N ≤ 100, 0 ≤ K ≤ 100, 1 ≤ i, j ≤ N