Hide

Speedrun

/problems/speedrun/file/statement/en/img-0001.jpg

You aspire to become a top Minecraft survival speedrunner. So, you need to come up with a strategy to do every necessary task quickly and efficiently. After watching a lot of previous world record speedruns, you noticed that the first day is the most crucial.

You need to finish at least $G$ tasks on the first Minecraft day for the speedrun to succeed. Each Minecraft day is $24\, 000$ ticks long, and thus to be a true gamer, you decided to do your math in Minecraft lingo. You can only work on one task at a time, and you cannot start another task before finishing your current task. Each task can only be done in a specific period of time $0 \leq t_{start} < t_{end} \leq 24\, 000$. Note: so long as the starting time of a task is greater than or equal to the end time of the previous task, the task can be scheduled with no conflict.

Given $G$, the minimum number of tasks you need to do on the first Minecraft day; $N$, the number of possible tasks you can do, and their corresponding time period, determine whether this run can be successful.

Input

The first line consists of $2$ space-separated integers, $0 < G \leq N < 10^5$, the number of tasks you need to do on the first day and the total number of tasks. The next $N$ lines each consist of $2$ integers $t_{start}$ and $t_{end}$, where $0 \leq t_{start} < t_{end} \leq 24\, 000$.

Output

Output “YES” if the run can be potentially successful, and “NO” otherwise.

Sample Input 1 Sample Output 1
2 3
0 20
20 24000
19 21
YES
Sample Input 2 Sample Output 2
2 4
3 5
1 4
4 24000
0 17000
YES
Sample Input 3 Sample Output 3
3 4
1 501
500 1001
1000 1501
1500 2000
NO
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 3.2medium
Statistics Show
Author
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in