시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 (언어별 추가 시간 없음) 1024 MB 168 42 37 35.238%

문제

형섭이는 세계에서 고작 K번째로 프로그래밍을 잘하지만, 최대한 많은 프로그래밍 대회에서 우승하여 자신의 이름을 알리고 싶어한다. 형섭이가 프로그래밍 대회에 참가하면 자기보다 잘하는 사람에게는 항상 지고 자기보다 못하는 사람은 항상 이긴다. 즉, 형섭이가 프로그래밍 대회에서 우승하려면 형섭이보다 잘하는 사람이 대회에 참가하지 않아야 하며 그런 대회에서는 형섭이가 항상 우승한다.

전세계에서는 총 N개의 프로그래밍 대회가 개최되며 각 대회는 Si일차부터 Ei일차까지 열린다. 대회가 열리는 장소가 다르므로 어느 누구라도 기간이 겹치는 대회는 동시에 참가할 수 없다. 형섭이는 자기보다 잘하는 K-1명의 사람들이 어떤 대회에 참가하는지 미리 알 수 있다. 형섭이는 K-1명이 참가하지 않는 대회들을 골라 최대한 많이 우승할 수 있도록 대회에 참가할 것이다.

만약 K-1명의 사람들이 적절하게 대회에 참가한다면 형섭이가 우승할 수 있는 대회가 얼마 없을 것이다. 형섭이는 그런 경우에 자신이 최대 몇 개의 대회에서 우승할 수 있는지 살펴보고자 한다. 대회의 정보가 주어질 때 형섭이가 우승할 수 있는 대회의 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 대회의 수 N (1 ≤ N ≤ 100,000), 형섭이의 등수 K (1 ≤ K ≤ 100,000)가 주어진다.

두 번째 줄부터 N개의 줄에는 대회의 시작 날짜 Si, 종료 날짜 Ei가 주어진다. (1 ≤ Si, Ei ≤ 1,000,000,000)

출력

형섭이가 우승할 수 있는 최대 대회 수가 가장 적어지도록 K-1명이 대회에 적절히 참가할 때, 형섭이가 우승할 수 있는 대회 수를 출력한다.

예제 입력 1

7 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

예제 출력 1

2

1등이 1, 4, 7번째 대회에 참여하면 형섭이는 최대 2개의 대회에서 우승할 수 있다. 1등이 1, 3, 5, 7번째 대회에 참여할 수 있지만 그러면 형섭이가 3개의 대회에서 우승할 수 있으므로 정답이 아니다.