27971번 - 강아지는 많을수록 좋다

문제

마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 $N$마리를 집에서 키우기로 결심했다!

호무라는 한 번의 행동에서 다음 2ドル$가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다.

• $A$-생성 마법: 강아지 $A$마리를 호무라의 집에 생성한다.
• $B$-생성 마법: 강아지 $B$마리를 호무라의 집에 생성한다.

그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 $M$개의 닫힌구간들 ${[L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]}$ 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 강아지가 사라지게 된다!

이를 명심하면서, 호무라는 위의 2ドル$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 호무라의 집에 정확히 $N$마리의 강아지가 있도록 만들고 싶다. 계산을 어려워하는 호무라를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 강아지의 수 $N (2\leq N\leq 100,000円),ドル 제약 사항에 해당하는 닫힌구간의 개수 $M (1\leq M\leq 100),ドル 그리고 $A$와 $B (1\leq A,B\leq N)$가 띄어쓰기로 구분되어 주어진다. 그 다음 $M$줄에 걸쳐서, 각 줄에 제약 사항에 해당하는 닫힌구간의 양 끝점이 주어진다. 1ドル\leq i\leq M$에 대하여 $L_i$와 $R_i$는 1ドル$ 이상 $N-1$ 이하의 정수이며, $L_i\leq R_i$이다.

출력

첫 번째 줄에 정확히 $N$마리의 강아지를 호무라의 집에 들일 수 있는 최소의 행동 횟수를 출력한다. 만약 불가능하다면 $-1$을 출력한다.

제한

힌트