시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB97303035.294%

문제

Ada, Bertrand and Charles often argue over which TV shows to watch, and to avoid some of their fights they have finally decided to buy a video tape recorder. This fabulous, new device can record k different TV shows simultaneously, and whenever a show recorded in one the machine’s k slots ends, the machine is immediately ready to record another show in the same slot.

The three friends wonder how many TV shows they can record during one day. They provide you with the TV guide for today’s shows, and tell you the number of shows the machine can record simultaneously. How many shows can they record, using their recording machine? Count only shows that are recorded in their entirety.

입력

The first line of input contains two integers n, k (1 ≤ k < n ≤ 100 000). Then follow n lines, each containing two integers xi, yi, meaning that show i starts at time xi and finishes by time yi. This means that two shows i and j, where yi = xj, can be recorded, without conflict, in the same recording slot. You may assume that 0 ≤ xi < yi ≤ 1 000 000 000.

출력

The output should contain exactly one line with a single integer: the maximum number of full shows from the TV guide that can be recorded with the tape recorder.

예제 입력 1

3 1
1 2
2 3
2 3

예제 출력 1

2

예제 입력 2

4 1
1 3
4 6
7 8
2 5

예제 출력 2

3

예제 입력 3

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

예제 출력 3

3

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2015 E번

  • 문제를 만든 사람: Markus S. Dregi, Pål G. Drange