| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 45 | 28 | 21 | 56.757% |
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.
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 $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 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 | 14 | $N ≤ 20$. |
| 2 | 17 | $N ≤ 300$. |
| 3 | 9 | $N ≤ 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. |
4 100 10 30 30 70 20 40 60 20
3
You can choose the 1ドル$-st, 2ドル$-nd and 4ドル$-th vaidilutės and arrange their shifts as follows:
1 100 30 40
-1
It is impossible to make a schedule since there is only one vaidilutė and she cannot work the whole day.