Hide

Problem G
Fire

Languages en is

In the old Baltic religion, it is important to have a holy fire burning. A priest called krivis is responsible for protecting it from extinguishing. He has many trustworthy helpers called vaidilutės, and wants to create a schedule for them to stoke and protect the fire. He has to ensure that the fire is always maintained by some vaidilutė.

Krivis has his own time measurement system, where each day has $M$ minutes. There are $N$ vaidilutės in his village. The $i$ -th vaidilutė’s possible work time are described by two integers $s_{i}$ and $e_{i}$ . The number $s_{i}$ is her own earliest time in the day when she may start working, and the number $e_{i}$ is the latest time of the day when she needs to finish working. Time is counted in minutes from the start of the day. Note that when $s_{i} > e_{i}$ , the vaidilutė is willing to work overnight.

Krivis asked you to choose some vaidilutės and arrange shifts for them. A chosen vaidilutė must start her shift not earlier than time $s_{i}$ , and end her shift not later than $e_{i}$ . A single shift is always shorter than the whole day. The chosen vaidilutės will repeat their shifts everyday.

Handing things over from one vaidilutė to the next increases the risk of the fire extinguishing. Because of this, you want to minimize the number of times this happens during the day and will arrange a schedule where the smallest possible number of vaidilutės is needed.

Task

Calculate the minimum number of vaidilutės that you need to choose, such that the holy fire is maintained at all times.

Input

The first line contains two integers $N$ and $M$ - the number of vaidilutės available and the length of the day in minutes.

Then $N$ lines follow. The $i$ -th of them contains two integers $s_{i}$ and $e_{i}$ - the earliest starting time and the latest finishing time of the $i$ -th vaidilutė.

Output

Output one integer - the minimum number of vaidilutės you need to choose. If it is impossible to choose the vaidilutės according to the requirements, output $- 1$ .

Constraints

$1 \leq N \leq 2 \cdot 10^{5}$
$2 \leq M \leq 10^{9}$
$0 \leq s_{i}, e_{i} < M$ (for all $1 \leq i \leq N$ )
$s_{i} \neq e_{i}$ (for all $1 \leq i \leq N$ )

Subtasks

No.	Points	Additional constraints
1	14	$N \leq 20$ .
2	17	$N \leq 300$ .
3	9	$N \leq 5 000$ .
4	13	For all vaidilutės, $s_{i} < e_{i}$ or $e_{i} = 0$ .
5	21	For each vaidilutė, the time interval from time $s_{i}$ until time $e_{i}$ has the same length.
6	26	No additional constraints.

Examples

In the first example you can choose the 1-st, 2-nd and 4-th vaidilutės and arrange their shifts as follows:

1-st vaidilutė works from the 10-th minute until the 30-th minute.
2-nd vaidilutė works from the 30-th minute until the 70-th minute.
4-th vaidilutė works from the 70-th minute until the 10-th minute on the following day.

In the second example it is impossible to make a schedule since there is only one vaidilutė and she cannot work the whole day.

Sample Input 1	Sample Output 1
4 100 10 30 30 70 20 40 60 20	3

Sample Input 2	Sample Output 2
1 100 30 40	-1

Problem GFire