405142: GYM101806 T Touch The Sky
Description
Figure: The house floats up in the sky by balloons. This picture is also used in 2018 KAIST RUN Spring Contest poster.
"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 Li and capacity Di, which indicates you can blow balloons in altitude at most Li, and the balloon busts after increasing the altitude by Di.
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!
InputThe first line contains N, the number of balloons. (1 ≤ N ≤ 250, 000)
In next N lines, the altitude limit of i-th balloon Li, and capacity of i-th balloon Di are given as two space-separated integers. (0 ≤ Li ≤ 1015, 1 ≤ Di ≤ 109)
OutputPrint the maximum number of balloons you can bust.
ExamplesInput3Output
30 10
30 20
30 30
3Input
4Output
0 10
2 4
5 3
8 2
3