Problem Description

We divide a day into \( M \) time slots, and there are \( N \) individuals, each willing to work during the time intervals \( (s_i, e_i) \). If \( s_i > e_i \), it means this person is willing to work until the \( e_i \) time slot of the next day, and no one will work continuously for more than one day.

You need to arrange some individuals to work such that their working hours cover the entire day. Determine the minimum number of people required.

Input Format

The first line contains two integers \( N \) and \( M \).

The next \( N \) lines each contain a pair of integers \( (s_i, e_i) \).

Output Format

Output a single number representing the minimum number of people to be arranged. If it is impossible to arrange people to cover the entire day, output \(-1\).

Sample Input and Output

Sample Input #1

4 100
10 30
30 70
20 40
60 20

Sample Output #1

3

Sample Input #2

1 100
30 40

Sample Output #2

-1

Notes

For the first sample, choosing individuals \( 1, 2, 4 \) works.

For the second sample, it is clearly impossible to cover the entire day.

For all data, \( 1 \leq N \leq 2 \times 10^5 \), \( 2 \leq M \leq 10^9 \), \( 0 \leq s_i, e_i < M \).

见题面 Input 部分

见题面 Output 部分