Description

FJ plans to assign his $N$ cows $(1 \le N \le 2.5\times 10^4)$ to do cleaning. He divides the day into $T(1 \le T \le 10^6)$ time slots. He wants every time slot to have a cow cleaning, while using as few cows as possible.

Input Format

The first line contains two integers $N$ and $T$.

The next $N$ lines each contain two integers, representing the time interval during which the $i$-th cow can work (inclusive).

Output Format

Output the minimum number of cows needed so that every time slot has a cow working. If it is impossible, output -1.

3 10
1 7
3 6
8 10

2

Hint

Sample explanation:

There are $3$ cows. The $1$-st can work during $1\sim7$, that is, starts at time $1$ and ends at time $7$ (time $7$ is also covered). The $2$-nd works during $3\sim6$, and the $3$-rd during $8\sim10$. Then only the $1$-st and the $3$-rd cows are needed to ensure every time slot is covered.

Translated by ChatGPT 5