题目描述

:::align{center}

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 has 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!

输入格式

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

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.

输出格式

Print the maximum number of balloons you can bust.

3
1 4
1 5
9 2

2

4
0 1
0 2
0 3
0 4

1

提示

Constraints

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