Entertainment Box

Description

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.

Input format

The first line of input contains two integers $n,k$ ($1\leq k < n \leq 100\ 000$). Then follow $n$ lines, each containing two integers $x_i,y_i$, meaning that show $i$ starts at time $x_i$ and finishes by time $y_i$. This means that two shows $i$ and $j$, where $y_i = x_j$, can be recorded, without conflict, in the same recording slot. You may assume that $0 \leq x_{i} < y_{i} \leq 1\ 000\ 000\ 000$.

Output format

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.

Input Sample 1

4 1
1 3
4 6
7 8
2 5

Output Sample 1

3

Input Sample 2

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

Output Sample 2

3

Input Sample 3

3 1
1 2
2 3
2 3

Output Sample 3

2

Hint

Consider

3 2 2 3 4 5 1 6

The correct anser is 3.

The following greedy strategy works: consider intervals in the order of ascending right endpoints, and whenever the next interval can be taken, then take it.

The problem is with checking the condition whether the next interval can be taken. The simple test right(Q[0]) <= left(A[i]) does not quite work, since it is too restrictive. Q[0] can finish before Q[1] starts, and thus one could possibly squeeze A[i] as well, as Q[0] and Q[1] do not add up in the capacity at any point.

The only way I see how to fix it at the current moment is to implement the checking condition on a counting tree / interval tree with + updates on intervals and max queries on intervals (both in log n time). Implementation of such a tree is pretty hardcore, so if we do not see any other solution, this increases the difficulty significantly.