소는 왜 길을 건너갔을까? 4 timer 2s memory 512MB

농부 존의 소들은 효율적으로 길을 건너는 방법을 터득하고 싶기에 오래전부터 길 건너기의 달인으로 유명한 닭의 도움을 받기로 했다.

안타깝게도 닭은 매우 바빠서 소를 도와줄 시간이 별로 없다. 농장에는 1번부터 C번까지 번호가 붙은 C마리의 닭과 1번부터 N번까지 번호가 붙은 N마리의 소가 있다.

i번 닭은 정확히 T_i초에만 소를 도와주고자 한다. 소는 비교적 스케줄에 여유가 있기에 j번 소는 A_j초부터 B_j초까지 길을 건널 수 있다. 즉, j번 소가 i번 닭의 도움을 받아 길을 건너려면  A_j ≤ T_i ≤ B_j를 만족해야 한다.

소는 최대 한 마리의 닭에게만 도움을 받을 수 있고, 닭 역시 최대 한 마리의 소만 도와줄 수 있을 때, 도움을 받을 수 있는 소가 최대 몇 마리인지 구해보자.