Problem J
Timely Treatments

Dr. Kassandra is a busy doctor in a hospital in Barcelona. She has $N$ patients waiting for treatment, where each patient $i$ requires $t_i$ time units for their treatment and must be fully treated by deadline $d_i$.

Kassandra can only treat one patient at a time. She starts working at time $0$ and can treat patients in any order, continuing without breaks if she wishes. Once she starts treating a patient, she must complete their treatment without interruption.

For example, if she has three patients:

• Patient 1: $t_1 = 3$, $d_1 = 5$

• Patient 2: $t_2 = 2$, $d_2 = 2$

• Patient 3: $t_3 = 1$, $d_3 = 3$

She could treat Patient $2$ first (finishing at time $2$), then Patient $3$ (finishing at time $3$). Note that Patient $3$ must be treated continuously for $1$ time unit, so starting at time $2$ means they would finish at time $3$. While Patient $1$ could theoretically be treated within their deadline if scheduled first, treating Patients $2$ and $3$ instead leads to the maximum possible number of treated patients.

Your task is to help Kassandra determine the maximum number of patients she can successfully treat while meeting their deadlines.

Input

The first line contains an integer $N$, the number of patients.

Each of the following $N$ lines contains two integers, $t_i$ and $d_i$, where $t_i$ is the time required to treat patient $i$, and $d_i$ is the deadline by which their treatment must be completed.

Output

Output a single integer: the maximum number of patients whose treatments can be completed by their respective deadlines when scheduled optimally.

Limits

• $1 \leq N \leq 10^6$

• $1 \leq t_i \leq 10^6$

• $1 \leq d_i \leq 10^9$

3
3 5
2 2
1 3

2

5
2 3
2 1
5 10
3 10
2 2

3