원형 우리에 덮개 씌우기

소들이 부끄러움을 많이 타서, 자신들이 이따금 모이는 원형 우리 둘레에 덮개를 둘러 주기를 바란다. 우리의 둘레 길이는 $C$이다($1 \le C \le 10^9$). 농부 John은 $M$개($1 \le M \le 10^5$)의 덮개 중에서 고를 수 있으며, 각 덮개는 시작 위치와 길이가 고정되어 있다. 이 덮개들을 적절히 고르면 우리 전체를 두를 수 있음이 보장된다.

$i$번 덮개는 정수 위치 $x_i$($0 \le x_i < C$)에 설치할 수 있다. 여기서 $x_i$는 우리 위의 고정된 기준점에서 시계 방향으로 잰 거리이다. 덮개의 길이는 정수 $l_i$($1 \le l_i \le C$)이며, $x_i$에서 시작해 시계 방향으로 $l_i$만큼 이어지는 연속된 호를 덮는다. 기준점을 지나면 우리를 한 바퀴 돌아 이어진다.

농부 John은 설치하는 덮개의 수를 최소로 하고 싶다. 우리의 둘레 전체를 덮는 데 필요한 덮개의 최소 개수를 구하여라.

둘레가 $5$인 우리를 생각하자. 아래 그림에서 두 개의 0은 우리 위의 같은 점을 나타낸다(1, 2, 3도 마찬가지이다). 사용할 수 있는 덮개는 세 개이다.

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

$2$번과 $3$번 덮개를 설치하면 둘레의 다섯 칸을 모두 덮을 수 있다. 덮개끼리 겹쳐도 문제가 없으므로 겹침은 신경 쓰지 않아도 된다.

• 첫째 줄에 두 정수 $C$와 $M$이 공백으로 구분되어 주어진다.
• 다음 $M$개의 줄 중 $i$번째 줄에는 $i$번 덮개를 나타내는 두 정수 $x_i$와 $l_i$가 공백으로 구분되어 주어진다.

• 우리의 둘레 전체를 덮는 데 필요한 덮개의 최소 개수를 정수 하나로 출력한다.