Maximum Projects Scheduling

You are given a set of projects. Each project is described by two integers: a deadline and a duration. Starting at time zero, you want to complete as many projects as possible. Projects must be performed sequentially one after another. A project can be completed if, when scheduled, the cumulative time plus its duration does not exceed its deadline. In other words, if the current time is t and the project takes d time, it can be done if:

$t + d \leq deadline$

You are required to select and schedule projects in an order that maximizes the number of projects completed without missing any deadlines. Use a greedy strategy (e.g. sorting by deadlines) to solve this problem.

inputFormat

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

 
 
...
 

Where n is the number of projects, and then n lines follow with two integers each representing the deadline and the duration of a project.

outputFormat

Output a single integer to standard output (stdout) — the maximum number of projects that can be completed under the given constraints.

4
10 5
8 3
15 7
7 2

3