Fire

문제

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 $MM$ minutes. There are $NN$ vaidilutės in his village. The $ii$-th vaidilutė's possible work time are described by two integers $s_{i}s\_i$ and $e_{i}e\_i$. The number $s_{i}s\_i$ is her own earliest time in the day when she may start working, and the number $e_{i}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}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}s\_i$, and end her shift not later than $e_{i}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.

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

입력

The first line contains two integers $NN$ and $MM$ – the number of vaidilutės available and the length of the day in minutes.

Then $NN$ lines follow. The $ii$-th of them contains two integers $s_{i}s\_i$ and $e_{i}e\_i$ – the earliest starting time and the latest finishing time of the $ii$-th vaidilutė.

출력

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

4 100
10 30
30 70
20 40
60 20

3

1 100
30 40

-1