Covering the Corral

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$ ($1 \le C \le 10^9$). Farmer John may choose from a set of $M$ ($1 \le M \le 10^5$) covers, each with a fixed starting position and length. At least one combination of covers can surround the entire corral.

Cover $i$ can be installed at integer position $x_i$ ($0 \le x_i < C$), measured as the clockwise distance from a fixed reference point on the corral, and has integer length $l_i$ ($1 \le l_i \le C$). It covers the continuous arc that starts at $x_i$ and extends $l_i$ units clockwise, wrapping around the corral if it passes the reference point.

Farmer John wants to install as few covers as possible. Determine the minimum number of covers needed to cover the entire circumference.

Consider a corral of circumference $5$, drawn below as a line in which both 0s mark the same point on the corral (and likewise for the 1s, 2s, and 3s). Three covers are available:

           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
            |..................|

Installing covers $2$ and $3$ spans all five units of the circumference. Overlap is allowed, so it causes no problems.

• The first line contains two space-separated integers $C$ and $M$.
• Each of the next $M$ lines contains two space-separated integers $x_i$ and $l_i$, describing cover $i$.

• Print a single integer: the minimum number of covers required to cover the entire circumference of the corral.