Touch the Sky

Time limit1sMemory limit1024 MB

Summary

Starting at altitude 0, each balloon i can be inflated only at altitude at most L_i, then raises the house by D_i and pops; maximize the number of balloons popped.

Level: Medium7 of 10
Topics: Greedy, Sorting, Heap, Intervals
Solved: No attempts yet

Problem

The photo shows a house lifted into the sky by balloons. It was also used on the poster of the 2018 KAIST RUN Spring Contest.

In the year 2117, professor Yu Jaemin built a linear time algorithm for TSP (Traveling Salesperson Problem). Every computer system collapsed soon after, and nuclear weapons left the world in ruins. You were the best expert in computer science, and you lost your work as well. You lost the meaning of your life long ago. Where did everything that used to make your heart beat go? After asking yourself that question without end, you reached one conclusion.

"If I go back to the KAIST where I first started ICPC, maybe I can find the meaning of my life."

The roads and the railways fell apart long ago. Still, you were a devoted ICPC contestant, and you keep the balloons you got at the Daejeon contest a hundred years ago. If only those balloons could lift your house.

You have $N$ balloons now, and you plan to tie them to the roof one at a time to lift your house into the sky. Balloon $i$ has an altitude limit $L_i$ and a capacity $D_i$ . Because of air pressure you can inflate this balloon only at an altitude of $L_i$ or lower, and this balloon raises the house by $D_i$ and then pops.

Your trip starts at altitude $0$ . Two or more inflated balloons would raise the house too fast, so you inflate one balloon, tie it to the roof, rise until it pops, then inflate another one and rise until that one pops, and you repeat this to lift the house. For convenience, assume the altitude does not change while you attach the next balloon after one pops. Only balloons change the altitude.

The final altitude does not matter. Each balloon carries the house a fixed distance before it pops, so popping as many balloons as you can is better. Find the maximum number of balloons you can pop.

Input

The first line contains the number of balloons $N$ .

The $i$ -th of the next $N$ lines contains two integers separated by a space, the altitude limit $L_i$ and the capacity $D_i$ of balloon $i$ .

Output

Print the maximum number of balloons you can pop on one line.

Constraints

$1 \le N \le 250\,000$
$0 \le L_i \le 10^{15}$
$1 \le D_i \le 10^9$

Examples2

Example 1
Input
```
3
1 4
1 5
9 2
```
Expected output
```
2
```
Example 2
Input
```
4
0 1
0 2
0 3
0 4
```
Expected output
```
1
```