在附近的幼儿园里，孩子们最近发明了一种深受喜爱的、考验力量和敏捷性的有趣游戏。

游戏场地是一个被划分为 $N \times N$ 个正方形网格的大型平坦区域。

孩子们在场地上放置大型海绵立方体。立方体的边长与网格正方形的边长相同。当立方体被放置在场地上时，它的边与某个网格正方形对齐。一个立方体也可以叠放在另一个立方体之上。

孩子们喜欢用立方体建造堡垒并躲在里面，但他们总是会留下一片狼藉。因此，在幼儿园放学前，老师们需要重新排列所有的立方体，使它们在场地上占据一个矩形区域，且该矩形区域内的每个网格正方形上恰好有一个立方体。

在一次移动中，可以将一个立方体从某个网格正方形的顶部移到任何其他网格正方形的顶部。

编写一个程序，在给定场地初始状态的情况下，计算将所有立方体排列成一个矩形所需的最少移动次数。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 100$，$1 \le M \le N^2$），分别表示场地的尺寸和当前场地上的立方体数量。

接下来的 $M$ 行，每行包含两个整数 $R$ 和 $C$（$1 \le R, C \le N$），表示包含该立方体的网格正方形的坐标。

输出格式

输出最少的移动次数。保证一定存在解。

样例

输入样例 1

3 2
1 1
1 1

输出样例 1

1

输入样例 2

4 3
2 2
4 4
1 1

输出样例 2

2

输入样例 3

5 8
2 2
3 2
4 2
2 4
3 4
4 4
2 3
2 3

输出样例 3

3

说明

在第一个样例中，只需将其中一个立方体从 $(1, 1)$ 移动到 $(1, 2)$ 或 $(2, 1)$ 即可。

在第三个样例中，将一个立方体从 $(2, 3)$ 移动到 $(3, 3)$，一个从 $(4, 2)$ 移动到 $(2, 5)$，另一个从 $(4, 4)$ 移动到 $(3, 5)$。