Peashooter and Zombies

Poor \(\color{black}\texttt{Q}\color{red}\texttt{wQcOrZ}\) encountered \(n\) zombies on the lawn. The \(i\)-th zombie appears at time \(l_i\) and will enter the house at time \(r_i\). \(\color{black}\texttt{Q}\color{red}\texttt{wQcOrZ}\) has \(m\) pea shooters. A pea shooter can kill the \(i\)-th zombie if it continuously attacks that zombie during the interval \((l_i, r_i)\) (both endpoints excluded). During an attack, the pea shooter cannot attack any other zombie, and once it starts attacking a zombie, it cannot switch targets.

Determine, under an optimal assignment of pea shooters to zombies, the minimum number of zombies that will enter the house.

Note: Two intervals \((l_i, r_i)\) and \((l_j, r_j)\) are non-overlapping if the finish time of one is less than or equal to the start time of the other, i.e. if \(r_i \le l_j\) (or vice versa). This is valid since the attack intervals are open at both endpoints.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)), representing the number of zombies and the number of pea shooters respectively.

Each of the next \(n\) lines contains two integers \(l_i\) and \(r_i\) (\(0 \le l_i < r_i \le 10^9\)), indicating that the \(i\)-th zombie appears at time \(l_i\) and enters the house at time \(r_i\).

outputFormat

Output a single integer: the minimum number of zombies that will enter the house under an optimal assignment of pea shooters.

sample

3 2
1 3
2 5
3 6

0