Maximum Task Scheduling

You are given a set of tasks. Each task is identified by an integer id and has an associated deadline.

Each task takes exactly 1 unit of time to complete. Starting at time 0, you process tasks one after another. A task can only be completed if the current time is strictly less than its deadline. Your goal is to determine the maximum number of tasks that can be completed before their deadlines.

Formally, if the tasks are processed in some order and the current time is incremented by 1 for each completed task, then a task with deadline \(d\) can be performed only if the time at which it starts is less than \(d\). The optimal solution is obtained by scheduling tasks in increasing order of deadlines.

inputFormat

The input is given via standard input (stdin) in the following format:

n
id_1 deadline_1
id_2 deadline_2
... 
id_n deadline_n

Here, n is a non-negative integer representing the number of tasks. Each of the following n lines contains two integers: the first is the task's id (which can be ignored for scheduling purposes) and the second is the deadline of the task.

outputFormat

Output a single integer on standard output (stdout) — the maximum number of tasks that can be completed by their deadlines.

1
1 1

1