회의실 배정

서울시립대학교 정보기술관에는 $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 ≤ N ≤ 200000; 1 ≤ K ≤ 3)$

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

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