경로 나누기

문제

농부 존의 소들은 밭에 있는 언덕 능선을 따라 자라는 클로버를 특히 좋아합니다. 클로버에 물을 주기 위해 존은 능선을 따라 스프링클러를 설치하려고 합니다.

능선을 $0$부터 $L$까지 이어지는 1차원 수직선으로 생각합니다($1 \le L \le 10^6$이며 $L$은 짝수입니다). 각 스프링클러는 이 수직선 위에 설치되며 좌우 양쪽으로 일정 거리만큼 물을 뿌립니다. 스프링클러의 분사 반경 $r$은 $A \le r \le B$를 만족하는 정수입니다($1 \le A \le B \le 1000$). 즉, 위치 $x$에 설치된 스프링클러는 닫힌 구간 $[x - r,\ x + r]$에 물을 줍니다.

존은 능선 전체에 물을 주되, 모든 지점이 정확히 하나의 스프링클러로만 덮이도록 해야 합니다(빈틈도 겹침도 없어야 합니다). 또한 어떤 스프링클러도 능선의 양 끝을 넘어서 물을 뿌릴 수 없습니다. 바꾸어 말하면, 스프링클러들은 구간 $[0, L]$을 연속한 구간들로 분할하며, 각 구간의 길이는 $2A$ 이상 $2B$ 이하의 짝수여야 합니다.

존의 소 $N$마리($1 \le N \le 1000$)는 각자 좋아하는 클로버 구간을 가지고 있으며, 이는 $S$부터 $E$까지의 구간으로 주어집니다(구간들은 서로 겹칠 수 있습니다). 각 소가 좋아하는 구간은 반드시 하나의 스프링클러가 물을 주어야 합니다(그 스프링클러가 구간 밖까지 물을 뿌리는 것은 상관없습니다). 바꾸어 말하면, 인접한 두 스프링클러의 경계가 어떤 소의 구간 $(S, E)$ 내부에(양 끝점을 제외하고) 들어가서는 안 됩니다.

능선 전체에 물을 주기 위해 필요한 스프링클러의 최소 개수를 구하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$과 $L$.
둘째 줄: 공백으로 구분된 두 정수 $A$와 $B$.
셋째 줄부터 $N+2$째 줄까지: 각 줄에 두 정수 $S$와 $E$($0 \le S < E \le L$)가 주어지며, 각각 한 소가 좋아하는 구간의 시작과 끝을 능선의 시작점으로부터의 거리로 나타냅니다.

출력

첫째 줄: 필요한 스프링클러의 최소 개수. 유효한 스프링클러 배치가 존재하지 않으면 $-1$을 출력합니다.

참고

첫 번째 예제를 살펴봅시다. 스프링클러 세 개면 충분합니다. 위치 $1$에 반경 $1$인 스프링클러($[0, 2]$를 덮음), 위치 $4$에 반경 $2$인 스프링클러($[2, 6]$을 덮음), 위치 $7$에 반경 $1$인 스프링클러($[6, 8]$을 덮음)입니다. 가운데 스프링클러는 둘째 소가 좋아하는 구간($3$부터 $6$까지) 전체에 물을 주고, 마지막 스프링클러는 첫째 소가 좋아하는 구간($6$부터 $7$까지) 전체에 물을 줍니다.

                 |-----c2----|-c1|       소가 좋아하는 구간

     |---1---|-------2-------|---3---|   스프링클러

     +---+---+---+---+---+---+---+---+

     0   1   2   3   4   5   6   7   8