농부 창호의 소들은 맛이 상당히 좋은 클로버들이 산마루에 일렬로 자라고 있는 것을 발견했다.

이 클로버들에게 물이 잘 공급되도록 하기 위해, 존은 스프링쿨러들을 설치하려고 한다.

설치를 쉽게 하기 위해, 이 스프링클러들은 각기 산마루에 일렬로 설치된다.

(쉽게 말해 길이L의 1차원 선분이라고 생각할 수 있다. 1≤L≤1,000,000이고 L은 짝수).

각 스프링클러는 설치된 위치에서 양 방향으로 정해진 거리만큼 물을 뿌린다.

이 거리는 정수 A..B 범위에 속하는데(1≤A≤B≤1000)이다.

창호는 모든 클로버들이 단 한 개의 스프링쿨러에만 물을 공급 받도록 하고 싶다.

또한, 창호는 물이 산마루의 양 끝을 넘는 범위에 뿌려지기 원치 않는다.

창호의 N마리(1≤N≤1000)소들은 각기 자신이 좋아하는 클로버들의 범위를 가지고 있다(서로의 선호하는 클로버 범위 구간들은 겹칠 수 있다).

이 범위는 닫혀있는 구간 (S,E)로 정의된다.

각 소들은 자신들이 좋아하는 범위 내의 클로버들에겐 한 개의 스프링클러에 의해서 물이 뿌려지기 원한다.

위 조건을 만족시키기 위해 필요한 최소의 스프링클러의 수를 구하시오.

경로나누기 timer 1s memory 128MB

경로나누기 1s 128MB