Description

The cows are so modest that they want Farmer John to install covers around the circular corral where they occasionally gather. The corral has circumference $C$ with $1 \le C \le 1{,}000{,}000{,}000$, and FJ can choose from a set of $M$ covers with $1 \le M \le 100{,}000$, each with a fixed starting point and size. It is guaranteed that at least one set of covers can surround the entire corral.

Cover $i$ can be installed at integer location $x_i$ (the distance from the starting point around the corral) with $0 \le x_i < C$, and has integer length $l_i$ with $1 \le l_i \le C$.

FJ wants to minimize the number of segments he must install. What is the minimum number of segments required to cover the entire circumference of the corral?

Consider a corral of circumference $5$, shown below as a pair of connected line segments where both '0's are the same point on the corral (as are both 1's, 2's, and 3's).

Three potential covering segments are available for installation:

Start   Length
i      x_i     l_i
1       0       1
2       1       2
3       3       3

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

As shown, installing segments 2 and 3 covers an extent of (at least) five units around the circumference. FJ has no trouble with overlap, so do not worry about that.

Input Format

• Line 1: Two space-separated integers $C$ and $M$.
• Lines $2..M+1$: Line $i+1$ contains two space-separated integers $x_i$ and $l_i$.

Output Format

• Line 1: A single integer, the minimum number of segments required to cover the entire circumference of the corral.

5 3 
0 1 
1 2 
3 3 

2 

Hint

Translated by ChatGPT 5