We all know the famous interval-scheduling problem. You have been given tasks, each of which will run between time and , inclusive, that you must tell your computer to run. You want to schedule the maximum number of tasks, under the condition that only one task can be run at any given point in time.
Your beloved spouse has gone ahead and assigned the tasks greedily. In particular, they will sort the tasks in order of increasing , and then increasing . Then, they will loop through tasks, and schedule the computer to run the current task if the previous assigned task does not overlap. If it does overlap, the current task is discarded and the next task will be tried.
You come along, and notice that your spouse has made a horrible mistake. Greedily assigning the tasks is not always optimal in trying to maximize the tasks ran!
Wanting to fix their mistake, but not having a lot of time to reprogram the computer, you want to remove at most (including) tasks that your spouse assigned the computer, and fill in the empty slot with a subset of the discarded tasks.
You want to maximize the number of tasks to be run after this change. Please output the maximum possible number of tasks to be run!
The first line will contain two integers, .
The next lines will each contain two integers, .
Output the maximum number of tasks to be run after your change.
Subtask 1 [5%]
Subtask 2 [25%]
Subtask 3 [70%]
No further constraints.
Sample Input 1
6 1 1 3 4 8 9 10 5 5 6 7 8 9
Sample Output 1
Explanation For Sample 1
Your spouse assigned tasks , , . You replace task with task and task , for a total of tasks run.
Sample Input 2
9 2 1 4 5 8 9 11 2 2 3 3 4 7 6 6 7 7 8 9
Sample Output 2
Sample Input 3
3 1 4 5 1 2 2 4
Sample Output 3