Building Repair Scheduling

In this problem, you are given \(N\) buildings. Each building \(i\) requires \(t_i\) time to repair and must be fully repaired by its deadline \(d_i\) (otherwise it will be ruined). There is only one repair worker who can instantly move from one building to another, but repairs must be performed sequentially. That is, the worker repairs one building and then moves on to the next.

Your task is to determine the maximum number of buildings that can be repaired if the worker follows an optimal repair schedule. The repair process is performed in a sequential order and the cumulative repair time up to any building must not exceed its deadline. More formally, if the buildings are repaired in some order and the cumulative repair time upon finishing a building is \(T\), then it must hold that \(T \le d_i\) for that building.

A common approach to this problem is to sort the buildings by their deadlines and use a greedy strategy with a max-heap (priority queue) to decide which repairs to perform.

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\)), representing the number of buildings.

Each of the following \(N\) lines contains two space-separated integers \(t_i\) and \(d_i\) (\(1 \le t_i \le 10^4\) and \(t_i \le d_i \le 10^9\)), where \(t_i\) is the time required to repair the \(i\)-th building and \(d_i\) is its deadline.

outputFormat

Output a single integer representing the maximum number of buildings that can be fully repaired by the repair worker following an optimal repair order.

sample

3
2 3
1 2
2 4

2