Corral Covering

Farmer John wants to cover a circular corral with circumference \(C\) using a set of \(M\) available covering segments. Each segment \(i\) can be installed starting at an integer position \(x_i\) (with \(0 \le x_i < C\)) and has an integer length \(l_i\). The segment covers the interval \([x_i, x_i+l_i)\) along the circumference. Note that since the corral is circular, the interval might wrap around.

The goal is to select as few segments as possible to completely cover the circular corral. It is guaranteed that at least one set of segments can cover the entire corral.

Input constraints:

• \(1 \le C \le 10^9\)
• \(1 \le M \le 10^5\)
• For each segment, \(0 \le x_i < C\) and \(1 \le l_i \le C\).

Hint: Because the corral is circular, one common approach is to "unwrap" the circle by duplicating the segments with their starting positions increased by \(C\) and then apply a greedy interval covering algorithm.

inputFormat

The first line contains two integers \(C\) and \(M\), the circumference of the corral and the number of available segments, respectively.

Each of the following \(M\) lines contains two integers \(x_i\) and \(l_i\), representing the starting point and length of the \(i\)-th segment.

outputFormat

Output a single integer representing the minimum number of segments required to cover the entire circumference of the corral.

sample

5 3
0 1
1 2
3 3

2