Fire

Time limit2sMemory limit1024 MB

Summary

Pick the fewest helper shifts, each inside its [s_i, e_i] window on a repeating M-minute day, so that every minute of the day is covered. Print -1 if impossible.

Level: Medium6 of 10
Topics: Intervals, Greedy, Sorting
Solved: No attempts yet

Problem

In the old Baltic religion, a holy fire must keep burning. A priest called krivis is responsible for keeping it from going out. He has many trustworthy helpers called vaidilutės, and he wants a schedule for them to stoke and guard the fire. At every moment, some vaidilutė must be keeping the fire alive.

Input

Krivis uses his own time system, where each day has $M$ minutes. There are $N$ vaidilutės in his village. The $i$ -th vaidilutė can work within a window given by two integers $s_i$ and $e_i$ . $s_i$ is the earliest minute of the day she may start, and $e_i$ is the latest minute by which she must finish. Time is counted in minutes from the start of the day. When $s_i > e_i$ , she is willing to work overnight.

Krivis asks you to choose some vaidilutės and arrange their shifts. A chosen vaidilutė must start her shift no earlier than $s_i$ and end it no later than $e_i$ . Every shift is shorter than a full day. The chosen vaidilutės repeat their shifts every day.

Each handover raises the risk that the fire goes out. Krivis wants few handovers during the day, and he wants a schedule that uses as few vaidilutės as possible.

Output

Output one integer, the minimum number of vaidilutės to choose so that the fire is maintained at all times. If it is impossible, output $-1$ .

Constraints

The first line contains $N$ and $M$ . Then $N$ lines follow, and the $i$ -th of them contains $s_i$ and $e_i$ .

Examples2

Example 1
Input
```
4 100
10 30
30 70
20 40
60 20
```
Expected output
```
3
```
Example 2
Input
```
1 100
30 40
```
Expected output
```
-1
```