测试数据来自 nnu_contest/1319

Limits

时间限制：3000ms

内存限制：128MB

Background

工程师小D研发出了一种激光枪，可用于清除障碍物。

Description

在平面直角坐标系的整点上，有$n$个可视为质点的障碍物，而小D可以在整个坐标系中随意移动。激光枪每次能够发射平行于$y=x$的激光束（可被视为几何学意义上的射线），其最大能量为$E_m$，而一束能量为$E$的激光最多能清除$E$个障碍物。

由于发射激光的代价昂贵，小D希望用最少的发射次数清除所有障碍，以减少花费。请帮小D算出这个最小次数。

Input

第$1$行：两个整数，$E_m,n$，含义见上。

第$2..n+1$行：每行两个整数$x_i,y_i$，各行依次表示第$i$个障碍物的位置坐标。

Output

仅一个数，表示清除所有障碍需要发射激光的最小次数。

Samples

Sample Input

2 4
1 1
2 2
3 3
1 2

Sample Output

3

Explanation

障碍物的位置如图所示。若小D站在$(0,0)$沿着$y=x$方向发射2次激光（强度分别为2和1），再站在$(0,1)$沿着$y=x$方向发射1次激光（强度为1），可以清除所有障碍物，且发射次数最小。

Data range

对于100%的数据，有$1≤E_m≤10^9,1≤n≤10^6,-10^6≤x_i,y_i≤10^6$。