페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7049
서브태스크

경비병 2초 1024MB

문제

동현이는 엄청난 보물 상자를 가지고 있다.

상자는 깊은 산 속 어딘가에 묻어두었지만 안심이 되지 않는 동현이는 경비병을 고용하기로 했다.

동현이가 사는 나라는 하루가 M시간이다.

하루는 0시에 시작해서 M-1시에서 1시간이 더 지나면 다시 0시가 된다.

(M이 24라면 우리가 사는 세상과 똑같다.)

경비병 후보는 총 N명이 있다.

i번째 사람을 고용하면 매일 s_i시부터 e_i시까지 보물 상자를 지켜줄 것이다. (양 끝 시간을 포함한다.)

만약 s_i > e_i 라면 밤을 새고 0시를 지나 e_i시가 될 때까지 지킨다는 의미이다.

동현이는 인건비를 아끼기 위해 최대한 적은 수의 경비병을 고용하려고 한다.

동시에 한 순간도 방심할 수 없기 때문에 매일 모든 시간 적어도 한 명의 경비병이 상자를 지키도록 할 것이다.

동현이는 몇 명의 경비병을 고용해야 할까?


입력

첫 줄에 N과 M이 주어진다.

i번째 줄에는 s_i, e_i가 주어진다.

<제한>

  • 1 \le N \le 200000

  • 2 \le M \le 10^9

  • 0 \le s_i, e_i < M

  • s_i \neq e_i


출력

동현이가 고용해야 하는 최소 경비의 수를 출력하라.

만약 어떻게 고용하더라도 보물을 완벽히 지킬 수 없다면 -1을 출력하라.


부분문제

번호 점수 조건
#114점

N \le 20

#217점

N \le 300

#39점

N \le 5000

#413점

모든 사람에 대해 s_i < e_i 이거나 e_i = 0

#521점

모든 사람의 매일 경비를 서는 시간의 길이는 동일하다.

#626점

추가적인 조건이 없다.


예제1

입력
4 100
10 30
30 70
20 40
60 20
출력
3

예제2

입력
1 100
30 40
출력
-1


출처

BOI 2024 D번

역링크 공식 문제집만