2419: Make it Manhattan

混乱的城市已经变得无法控制。大楼随处乱造，城市的布局也是一片混乱。市长决定要结束这种局面，并且想建造一个漂亮的、有组织的城市。

通过一些研究，他找到了使这个成为现实的理想的方法。受到纽约曼哈顿的启发，他希望所有的房子都造在矩形的格子里，用南北向的林荫道和东西向的街道隔开。这些林荫道和街道都有相同的间距。

在现在这种状况，房子已经规划在矩形格子里面了。事实上，每幢房子都恰好完全覆盖住一个矩形格子。但是，所有的楼房随机地散落在城市里，不毁坏房屋来造路是不可能的。为了使得更多的市民开心，市长想要毁坏尽量少的房子。给你当前的房屋建造状况，最小破坏量是多少呢？

上图说明了这个问题。阴影方块是原先的楼房。如果道路间距为3，上面的粗线条就是规划的道路，被经过的那个楼房就要被拆除了。

输入文件的第一行为两个整数D和N，用一个空格隔开，分别代表道路间距、城市中的楼房数，1 <= D <= 1000, 1 <= N <= 100000。

以下N行，每行两个整数x和y，用一个空格隔开，代表房屋的位置。-109 <= x,y <= 109。

输出文件只有一行一个整数，代表最少需要毁坏的房屋数。

3 10 
1 0 
2 0 
3 0 
4 0 
1 2 
0 3 
1 5 
3 5 
4 2 
-2 2 

1