题目描述

奶牛们非常谦逊，它们想让农夫约翰在它们偶尔聚集的圆形围栏周围安装覆盖物。围栏的周长为 $C$。FJ 可以从 $M$ 个覆盖物中进行选择，每个覆盖物都有固定的起点和长度。题目保证至少有一组覆盖物可以覆盖整个围栏。

覆盖物 $i$ 可以安装在整数位置 $x_i$（从围栏起点沿圆周的距离），其有整数长度 $l_i$。

FJ 想要最小化他必须安装的覆盖物数量。覆盖整个围栏圆周所需的最少覆盖物数量是多少？

考虑一个周长为 $5$ 的围栏，如下图所示，它由两条相连的线段表示，其中两个“0”是围栏上的同一个点（两个“1”、“2”和“3”也是同样的情况）。

有三个可用的覆盖段可供安装：

编号    起点 x_i    长度 l_i
1         0           1
2         1           2
3         3           3

0   1   2   3   4   0   1   2   3  ...
围栏: +---+---+---+---+--:+---+---+---+- ...
11111               1111
22222222            22222222
333333333333
|..................|

如图所示，安装覆盖段 2 和 3 可以覆盖圆周上（至少）5 个单位的范围。FJ 不担心覆盖段重叠的问题，所以不必为此担心。

输入格式

第一行两个空格分隔的整数 $C$ 和 $M$。

从第 $2$ 到第 $M+1$ 行，第 $i+1$ 行包含两个空格分隔的整数 $x_i$ 和 $l_i$。

输出格式

一行一个整数，覆盖整个围栏圆周所需的最少覆盖段数量。

5 3 
0 1 
1 2 
3 3 

2 

提示

对于 $100\%$ 的数据，有 $1 \le C \le 10^9,1 \le M \le 10^5, 0 \le x_i < C,1 \le l_i \le C$。