Placeholder

#7049
서브태스크

경비병 2초 1024MB

문제

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

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


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

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

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


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

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

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


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

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


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


입력

첫 줄에 NNMM이 주어진다.

ii번째 줄에는 si,eis_i, e_i가 주어진다.


<제한>

  • 1N2000001 \le N \le 200000

  • 2M1092 \le M \le 10^9

  • 0si,ei<M0 \le s_i, e_i < M

  • sieis_i \neq e_i


출력

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

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


부분문제

번호 점수 조건
#114점

N20N \le 20

#217점

N300N \le 300

#39점

N5000N \le 5000

#413점

모든 사람에 대해 si<eis_i < e_i 이거나 ei=0e_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번


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.