P10762 [BalticOI 2024] Fire

Translated from [BalticOI 2024 Day2 T1](https://boi2024.lmio.lt/tasks/d2-fire-statement.pdf).

We divide one day into $M$ time units. There are $N$ people, and person $i$ is willing to work during $[s_i, e_i)$. If $s_i > e_i$, it means this person is willing to work until time $e_i$ on the next day. Each person’s maximum continuous working time does not exceed one full day. You need to arrange some people to work so that their working time can cover the whole day. Find the number of people needed.

The first line contains two integers $N, M$. The next $N$ lines each contain a pair $(s_i, e_i)$.

Output one integer, the minimum number of people to arrange. If it is impossible to arrange people so that the whole day is covered, output $-1$.

For the first sample, choose $1, 2, 4$. For the second sample, there is clearly no solution. | Subtask ID | Special Property | Score | | :-----------: | :----------- | :-----------: | | $1$ | $N \leq 20$ | $14$ | | $2$ | $N \leq 300$ | $17$ | | $3$ | $N \leq 5000$ | $9$ | | $4$ | Guaranteed $s_i < e_i$ or $e_i = 0$ | $13$ | | $5$ | Guaranteed that everyone has the same working time interval | $21$ | | $6$ | No special property | $26$ | For all testdata, $1 \leq N \leq 2 \times 10^5$, $2 \leq M \leq 10^9$, $0 \leq s_i, e_i < M$, $s_i \ne e_i$. Translated by ChatGPT 5