fire — BOI contest
Task type: batch | Time limit: 1 s | Memory limit: 256 MB | Difficulty: 19
Algorithms: sparse table, data structures, greedy, coordinate compression

# Fire

![](_page_0_Picture_0.jpeg)

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 is described by two integers *s<sub>i</sub>* and *e<sub>i</sub>*. The number *s<sub>i</sub>* is her own earliest time in the day when she may start working, and the number *e<sub>i</sub>* 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<sub>i</sub>* > *e<sub>i</sub>*, 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<sub>i</sub>*, and end her shift not later than *e<sub>i</sub>*. 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<sub>i</sub>* and *e<sub>i</sub>* – 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.

### Examples

| Input          | Output | Explanation                                                                                                                                                                                                                                                                                       |
|----------------|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `4 100`        | 3      | You can choose the 1-st, 2-nd and 4-th vaidilutės and arrange their shifts as follows:                                                                                                                                                                                                          |
| `10 30`        |        | • 1-st vaidilutė works from the 10-th minute until the 30-th minute.                                                                                                                                                                                                                            |
| `30 70`        |        | • 2-nd vaidilutė works from the 30-th minute until the 70-th minute.                                                                                                                                                                                                                            |
| `20 40`        |        | • 4-th vaidilutė works from the 70-th minute until the 10-th minute on the following day.                                                                                                                                                                                                           |
| `60 20`        |        |                                                                                                                                                                                                                                                                                               |
| `1 100`        | -1     | It is impossible to make a schedule since there is only one vaidilutė and she cannot work the whole day.                                                                                                                                                                                          |
| `30 40`        |        |                                                                                                                                                                                                                                                                                               |

## Constraints

- 1 ≤ *N* ≤ 2 ⋅ 10<sup>5</sup>
- 2 ≤ *M* ≤ 10<sup>9</sup>
- 0 ≤ *s<sub>i</sub>*, *e<sub>i</sub>* < *M* (for all 1 ≤ *i* ≤ *N*)
- *s<sub>i</sub>* ≠ *e<sub>i</sub>* (for all 1 ≤ *i* ≤ *N*)

### Subtasks

| No. | Points | Additional constraints                                                                          |
|-----|--------|-------------------------------------------------------------------------------------------------|
| 1   | 14     | \(N \leq 20\)                                                                                 |
| 2   | 17     | \(N \leq 300\)                                                                                |
| 3   | 9      | \(N \leq 5000\)                                                                               |
| 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.                                                                    |

Starter code: