30827번 - 회의실 배정

문제

서울시립대학교 정보기술관에는 $K$개의 회의실이 있고, 이 회의실을 사용하려는 회의 $N$개가 있다.

서울시립대학교 정보기술관 회의실의 규칙은 다음과 같다.

• 두 개 이상의 회의를 한 회의실에서 동시에 진행할 수 없다.
• 회의실을 치우는 시간이 필요하기 때문에 회의가 끝난 즉시 같은 회의실에서 다른 회의를 시작할 수 없다.

다시 말해, 어떤 두 회의 $A,ドル $B$에 대해 두 회의의 시작 시간을 각각 $A_s,ドル $B_s,ドル 두 회의의 종료 시간을 각각 $A_e,ドル $B_e$라고 할 때 $A_e < B_s$ 또는 $B_e < A_s$를 만족해야 두 회의를 같은 회의실에서 진행할 수 있다.

회의실을 사용하려는 회의 $N$개의 회의 시작 시간 $(i_s)$와 종료 시간$(i_e)$가 주어질 때, 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

입력

첫 번째 줄에 회의의 수 $N$과 회의실의 수 $K$가 주어진다. $(1 \leq N \leq 200\ 000; 1 \leq K \leq 3)$

두 번째 줄부터 $N+1$ 번째 줄까지 각 회의의 시작 시간 $s_i$와 종료 시간 $e_i$가 공백으로 구분되어 양의 정수로 주어진다. $(1 \leq i_s, i_e \leq 10^{9})$

출력

회의실에서 진행할 수 있는 회의의 최대 개수를 출력한다.

제한

힌트