Entertainment Box

Interview

Time limit2sMemory limit256 MB

Summary

Schedule the most TV shows on k recorders so no recorder tapes overlapping shows.

Level: Medium5 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

Ada, Bertrand and Charles argue often about which TV shows to watch. To cut down on the fights they bought a video recorder. The recorder tapes $k$ different shows at the same time, and as soon as a show being taped in one of its $k$ slots ends, that slot is ready to tape another show.

The three friends want to know how many shows they can record in one day. You get today's TV guide and the number of shows the machine tapes at once. Find the largest number of shows they can record. Only shows taped from start to finish count.

Input

The first line contains two integers $n$ and $k$ ( $1 \le k < n \le 100\,000$ ). Each of the next $n$ lines contains two integers $x_i$ and $y_i$ , meaning that show $i$ starts at time $x_i$ and finishes at time $y_i$ . Two shows $i$ and $j$ with $y_i = x_j$ can be taped in the same slot without conflict. It holds that $0 \le x_i < y_i \le 1\,000\,000\,000$ .

Output

Print one line with a single integer, the maximum number of full shows from the guide that the recorder can tape.

Examples3

Example 1
Input
```
3 1
1 2
2 3
2 3
```
Expected output
```
2
```
Example 2
Input
```
4 1
1 3
4 6
7 8
2 5
```
Expected output
```
3
```
Example 3
Input
```
5 2
1 4
5 9
2 7
3 8
6 10
```
Expected output
```
3
```