Maximizing the Number of Tasks Completed with Start Time Constraints

Bessie the cow has (N) tasks to complete. The (i)th task can be started at any time, but if you decide to do it, you must begin no later than time (s_i) and it takes (t_i) time to finish. Formally, if you choose to perform task (i), you must start it at some time (T) satisfying (T \le s_i), and then you will be busy for (t_i) units of time. You start at time (0), and once a task is started you must work on it continuously until it is finished (i.e. you cannot work on other tasks in between).

Your goal is to choose a subset of tasks and arrange them in some order so that each task's starting time (the total time spent on tasks scheduled before it) is at most its allowed start deadline (s_i). What is the maximum number of tasks you can complete?

Note: All formulas are given in (\LaTeX) format. For every chosen set of tasks, there must exist a permutation (\pi) such that for every (k) (with (1 \le k \le \lvert\pi\rvert)), if (P_k = \sum_{j=1}^{k-1} t_{\pi(j)}) is the start time of the (k)th task in that order then we have [ P_k \le s_{\pi(k)}. ]

inputFormat

The input begins with a single integer (N) ((1 \le N \le 2\cdot10^5)) on the first line representing the number of tasks. Each of the following (N) lines contains two space‐separated integers (s_i) and (t_i) ((0\le s_i \le 10^{18}), (1\le t_i \le 10^{18})), representing the latest time by which task (i) must be started and its processing time, respectively.

outputFormat

Output a single integer representing the maximum number of tasks that can be completed.

sample

2
1 100
100 1

2