Financial Planning#9883
Being a responsible young adult, you have decided to start planning for retirement. After some back-of-the-envelope calculations, you have figured out that you need at least euros to retire comfortably.
You are currently broke, but fortunately a generous gazillionaire friend has offered to lend you as much money as you need, interest-free, to invest in the stock market. Once you have made some profit, you will return the borrowed sum to your friend and keep the rest.
You have investment opportunities available, the -th of which costs c_i euros. Using your computer science skills, you have also predicted that the -th investment will earn you p_i euros per day. You can invest in each opportunity at most once, but you may invest in as many different opportunities as you like. 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 euros), you will earn p_2 = 10 euros per day. After two days you will have earned euros, which is exactly enough to repay your friend the euros you borrowed and retire with the remaining euros of profit. There is no way to earn a net profit of euros in a single day, so two days is the best possible answer.
The first line contains the number of investment opportunities n~(1 \le n \le 10^5) and the minimum amount of money m~(1 \le m \le 10^9) you need to retire.
Each of the next lines contains two integers: the daily profit p_i~(1 \le p_i \le 10^9) of the -th investment and its initial cost c_i~(1 \le c_i \le 10^9).
Print the minimum number of days needed to repay your friend and retire with at least euros, assuming you follow an optimal investment strategy.
Example 1
Example 2
Example 3