Background

After finishing today’s tricky 3D computational geometry, $\color{black}\texttt{Q}\color{red}\texttt{wQcOrZ}$ opened an interesting exe file.

Problem Description

The unlucky $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ encountered $n$ zombies on the lawn. Zombie $i$ appears at time $l_i$ and will enter the house at time $r_i$.

$\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ has $m$ Peashooters. If a Peashooter keeps attacking zombie $i$ continuously during the time interval from $l_i$ to $r_i$ (excluding both endpoints), then it can kill zombie $i$. However, during the attack it cannot attack any other zombie, and the target zombie cannot be changed.

Now $\color{black}\texttt Q\color{red}\texttt{wQcOrZ}$ wants to know: with a proper schedule, what is the minimum number of zombies that will enter his house.

Input Format

The first line contains two integers $n, m$, representing the number of zombies and the number of Peashooters.

The next $n$ lines each contain two integers $l_i$ and $r_i$, representing the time when zombie $i$ appears and the time when it enters the house.

Output Format

Output one integer representing the answer.

2 1
1 2
3 4

0

3 2
1 3
1 3
2 4

1

2 1
1 3
3 5

0

Hint

For $30\%$ of the testdata, $n, m \leq 6$.
For $60\%$ of the testdata, $n, m \leq 10^3$.
For another $20\%$ of the testdata, $m \geq n$.
For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^5$, $1 \leq l_i < r_i \leq 10^9$.

Translated by ChatGPT 5