405142: GYM101806 T Touch The Sky

T. Touch The Skytime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Figure: The house floats up in the sky by balloons. This picture is also used in 2018 KAIST RUN Spring Contest poster.

In the year 2117, Professor Jaemin Yu developed a linear-time algorithm for TSP(Traveling Salesperson Problem). Not long after that happened, all computer systems were destroyed, and nuclear weapons demolished all the lands. You, a great computer expert, also lost your job. With a great despair, you lost your meaning of life long ago. All those things that made your heart beat – where had they gone? After questioning yourself again and again, your conclusion is ...

"If I go to KAIST where I started my first ICPC, can I find a meaning of my life?"

All transportations were destroyed, but you were an avid ICPC participant, and you collected a lot of century-old balloons in Korean Regionals. If you could float a house with some of those balloons...

Currently you have N balloons, and you are trying to float the house into the sky by attaching balloons on the rooftop. Every balloon have altitude limit L_i and capacity D_i, which indicates you can blow balloons in altitude at most L_i, and the balloon busts after increasing the altitude by D_i.

Your journey starts at altitude 0. If you have more than 1 balloons enlarged, then the house will ascend too fast. Thus, you will blow one balloon and attach it at the rooftop, increase the altitude until the balloons bust, blow the other balloon and attach it to increase the altitude... to make your house float. For convenience, you may assume that balloons can only increase the altitude.

You don't care about your final altitude, but a balloon can move a fixed amount of distance. Thus, you want to bust as many balloons as possible. You want to calculate a maximum number of balloons you can bust, and check if you can make a journey to KAIST. Let's see whether your 100-year-old ICPC experience can help on this problem!

Input

The first line contains N, the number of balloons. (1 ≤ N ≤ 250, 000)

In next N lines, the altitude limit of i-th balloon L_i, and capacity of i-th balloon D_i are given as two space-separated integers. (0 ≤ L_i ≤ 10¹⁵, 1 ≤ D_i ≤ 10⁹)

Output

Print the maximum number of balloons you can bust.

ExamplesInput

3
30 10
30 20
30 30

Output

3

Input

4
0 10
2 4
5 3
8 2

Output

3