USACO 2004 December Gold Dividing the Path- 경로나누기 > 문제은행 : 정보올림피아드&알고리즘




1633 : 경로나누기

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
3 회   
시도횟수
10 회   

문제

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

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

 

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

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

 

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

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

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

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

 

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

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

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

 

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

 


입력형식

입력 파일의 첫 줄에 N과 L이 공백을 사이에 두고 주어진다. 둘째 줄에는 A와 B가 주어지며, 셋째 줄부터 각 소들의 S, E가 주어지는데 0 ≤ S < E ≤ L 이다.

출력형식

출력 파일에는 최소로 필요한 스프링클러의 수를 출력하며, 불가능하면 -1 출력한다.

입력 예

2 8
1 2
6 7
3 6

출력 예

3

Hint!

입력 설명: 소 두마리가 있고 산마루의 길이는 8이다. 스프레이는 길이가 1 혹은 2인 것들만 있다. 소 한마리는 3-6구간을 다른 것은 6-7구간의 클로버를 좋아한다. 출력 설명: 아래의 그림처럼 스프링 쿨러 3개가 저렇게 물을 주면 조건을 만족하면서 최소이다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP