Problemas
농부 창호의 소들은 맛이 상당히 좋은 클로버들이 산마루에 일렬로 자라고 있는 것을 발견했다.
이 클로버들에게 물이 잘 공급되도록 하기 위해, 존은 스프링쿨러들을 설치하려고 한다.
설치를 쉽게 하기 위해, 이 스프링클러들은 각기 산마루에 일렬로 설치된다.
(쉽게 말해 길이L의 1차원 선분이라고 생각할 수 있다. 1≤L≤1,000,000이고 L은 짝수).
각 스프링클러는 설치된 위치에서 양 방향으로 정해진 거리만큼 물을 뿌린다.
이 거리는 정수 A..B 범위에 속하는데(1≤A≤B≤1000)이다.
창호는 모든 클로버들이 단 한 개의 스프링쿨러에만 물을 공급 받도록 하고 싶다.
또한, 창호는 물이 산마루의 양 끝을 넘는 범위에 뿌려지기 원치 않는다.
창호의 N마리(1≤N≤1000)소들은 각기 자신이 좋아하는 클로버들의 범위를 가지고 있다(서로의 선호하는 클로버 범위 구간들은 겹칠 수 있다).
이 범위는 닫혀있는 구간 (S,E)로 정의된다.
각 소들은 자신들이 좋아하는 범위 내의 클로버들에겐 한 개의 스프링클러에 의해서 물이 뿌려지기 원한다.
위 조건을 만족시키기 위해 필요한 최소의 스프링클러의 수를 구하시오.
Entrada
입력 파일의 첫 줄에 N과 L이 공백을 사이에 두고 주어진다.
둘째 줄에는 A와 B가 주어지며, 셋째 줄부터 각 소들의 S, E가 주어지는데 0 ≤ S < E ≤ L 이다.
Salida
출력 파일에는 최소로 필요한 스프링클러의 수를 출력하며, 불가능하면 -1 출력한다.
Ejemplo
2 8
1 2
6 7
3 6
3
Pista
Fuente
USACO 2004 December Gold Dividing the Path
Debes iniciar sesión para escribir código.