Description

There are $T(1\le T\le 10^6)$ time slots in a day. John plans to schedule his $N(1\le N\le 2.5\times 10^4)$ cows to be on duty to clean the barn. Each cow has her own available interval $[S_i,E_i](1\le S_i\le E_i\le T)$ and only cows who are free can be scheduled. Moreover, every time slot must have a cow on duty.

What is the minimum number of cows required to cover all time slots? If it is impossible to make a valid schedule, output $-1$.

Input Format

The first line: $N$, $T$.

Lines $2$ to $N+1$: $S_i$, $E_i$.

Output Format

One line, output the minimum number of cows.

3 10
1 7
3 6
6 10

2

Hint

$1\le T\le 10^6$，$N\le 2.5\times 10^4$，$1\le S_i\le E_i\le T$。

$\text{Update On 2023/08/08}$：Added a set of hack testdata, see details here. Ruled out wrong solutions with time complexity $\mathcal O(nt)$.

Translated by ChatGPT 5