Contest Balloons
Contest: Canada Cup 2016
Difficulty rating: 1800
Tags: data structures, greedy

One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they have. It means that one's place is equal to the number of teams with more balloons, increased by 1. For example, if there are seven teams with more balloons, you get the eight place. Ties are allowed.

You should know that it's important to eat before a contest. If the number of balloons of a team is greater than the weight of this team, the team starts to float in the air together with their workstation. They eventually touch the ceiling, what is strictly forbidden by the rules. The team is then disqualified and isn't considered in the standings.

A contest has just finished. There are n teams, numbered 1 through n. The i-th team has ti balloons and weight wi. It's guaranteed that ti doesn't exceed wi so nobody floats initially.

Limak is a member of the first team. He doesn't like cheating and he would never steal balloons from other teams. Instead, he can give his balloons away to other teams, possibly making them float. Limak can give away zero or more balloons of his team. Obviously, he can't give away more balloons than his team initially has.

What is the best place Limak can get?

Input format:
The first line of the standard input contains one integer n (2 ≤ n ≤ 300 000) — the number of teams.

The i-th of n following lines contains two integers ti and wi (0 ≤ ti ≤ wi ≤ 1018) — respectively the number of balloons and the weight of the i-th team. Limak is a member of the first team.

Output format:
Print one integer denoting the best place Limak can get.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample, Limak has 20 balloons initially. There are three teams with more balloons (32, 40 and 45 balloons), so Limak has the fourth place initially. One optimal strategy is:

1. Limak gives 6 balloons away to a team with 32 balloons and weight 37, which is just enough to make them fly. Unfortunately, Limak has only 14 balloons now and he would get the fifth place.
2. Limak gives 6 balloons away to a team with 45 balloons. Now they have 51 balloons and weight 50 so they fly and get disqualified.
3. Limak gives 1 balloon to each of two teams with 16 balloons initially.
4. Limak has 20 - 6 - 6 - 1 - 1 = 6 balloons.
5. There are three other teams left and their numbers of balloons are 40, 14 and 2.
6. Limak gets the third place because there are two teams with more balloons.

In the second sample, Limak has the second place and he can't improve it.

In the third sample, Limak has just enough balloons to get rid of teams 2, 3 and 5 (the teams with 81 000 000 000, 5 000 000 000 and 46 000 000 000 balloons respectively). With zero balloons left, he will get the second place (ex-aequo with team 6 and team 7).

Example input:
8
20 1000
32 37
40 1000
45 50
16 16
16 16
14 1000
2 1000

Example output:
3

Example input:
7
4 4
4 4
4 4
4 4
4 4
4 4
5 5

Example output:
2

Editorial:
I (a problem author) want to thank the ICPC Live staff. During the World Finals a commentator ([user:Egor] maybe?) said that contests always have balloons and maybe someone should invent a problem about them for the next finals (I'm not organizing those though). Thanks for the idea!
If you just want the solution, read only the last paragraph. Previous ones describe how to find a correct approach. It may lead to a slightly more complicated solution, but you will learn something for sure.
To come up with a solution, you must try iterating over some value or maybe binary searching an optimal value. Let's list a few reasonable ideas. Try to binary search the answer (for fixed final place of Limak you must say if he can get at least this place). Or iterate over the number of disqualified teams (if Limak should beat exactly i teams, what is the best place he can get?). Or iterate over the number of balloons Limak should give away.
The last idea turns out to be fruitful. The first observation is that you don't have to consider every possible number of balloons to give away. We can assume that the final number of balloons will be either 0 or ti for some i. Otherwise Limak could give away some more balloons and his place won't be worse (if there are no more teams, let's imagine he can destroy them). We use here a simple observation that the i-th team either will be disqualified or will still have exactly ti balloons, i.e. values ti won't change.
We have O(n) possibilities for the final number of balloons. Let's first solve a problem in $${ \mathcal { O } } ( n ^ { 2 } \cdot \log n )$$ by considering possibilities separately, each in $${ \mathcal { O } } ( n \cdot \log n )$$. Let's say Limak will have k balloons at the end. He can give away t1 - k balloons. He should try to get rid of teams with ti > k because worse teams don't affect his place. You should sort teams with ti > k by the number of balloons they need to get disqualified i.e. wi - ti + 1. It's easiest for Limak to get rid of teams with small value of wi - ti + 1 so you should just check how many of those values can be chosen so that the sum of them won't exceed t1 - k. It turns out to be possible to improve the above by considering possibilities in the decreasing order. Think what happens when you decrease k. Some more teams become a possible target and you should consider their values wi - ti + 1. A sorted set of those values should be useful. Try to invent a solution yourself now. Then you can see one simple version in the next paragraph.
Now let's see an $${ \mathcal { O } } ( n \cdot \log n )$$ greedy solution. Create a variable k representing the final number of balloons Limak has, initially k = t1. Create and maintain a multiset with values wi - ti + 1 of teams better than the current k, i.e. teams with ti > k. If it makes sense to give away some more balloons, Limak has to eliminate at least one of those better teams (otherwise he can stop now). It's easiest to eliminate a team with the smallest wi - ti + 1, so we can just remove the smallest element from the set and decrease k by its value. Maybe some more teams become better than the current k and you should add those to the multiset. Note that the multiset contains exactly those teams which would win with Limak in the current scenario, so after every change of k you can update the answer 'ans = min(ans, my_multiset.size() + 1)'. Remember to stop if k becomes smaller than 0.