Financial Planning
Time limit3sMemory limit512 MB
Given investments with cost and daily profit, find 0 or more to buy after borrowing, minimizing days d until total profit times d exceeds total cost plus M.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Math, Binary search
- Solved
- No attempts yet
Problem
As a responsible young adult, you have decided to start planning for retirement. From some rough calculations, you determined that you need at least M euros to retire comfortably.
You are currently broke, but fortunately a generous billionaire friend has offered to lend you an arbitrary amount of money (as much as you need), without interest, to invest in the stock market. After earning some profits, you will return the original sum to your friend and keep the remainder.
You have n investment opportunities available, and the i-th one costs ci euros. Using your computer science skills, you predicted that the i-th investment earns pi euros per day. What is the minimum number of days you need before you can pay back your friend and retire?
For example, consider the first sample. If you buy only the second investment (which costs 15 euros), you earn p2 = 10 euros per day. After two days you have earned 20 euros, exactly enough to pay back your friend (from whom you borrowed 15 euros) and retire with the remaining profit (5 euros). There is no way to make a net amount of 5 euros in a single day, so two days is the fastest possible.
Input
The first line contains the number of investment options 1 ≤ n ≤ 105 and the minimum amount of money you need to retire 1 ≤ M ≤ 109.
Then n lines follow. Each line i has two integers: the daily profit of this investment 1 ≤ pi ≤ 109 and its initial cost 1 ≤ ci ≤ 109.
Output
Print the minimum number of days needed to recoup your investments and retire with at least M euros, if you follow an optimal investment strategy.