Background

Translated from BalticOI 2024 Day2 T1.

Problem Description

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.

Input Format

The first line contains two integers $N, M$.

The next $N$ lines each contain a pair $(s_i, e_i)$.

Output Format

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$.

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1

Hint

For the first sample, choose $1, 2, 4$.

For the second sample, there is clearly no solution.

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