레이팅 미적용-3mm
-15mm
Being a responsible young adult, you have decided to start planning for retirement. Doing some back-of-the-envelope calculations, you figured out you need at least \(M\) euros to retire comfortably.
You are currently broke, but fortunately a generous gazillionaire 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 making some profits you will then return the original sum to your friend, leaving you with the remainder.
Available to you are \(n\) investment opportunities, the \(i\)-th of which costs \(c_i\) euros. You also used your computer science skills to predict that the \(i\)-th investment will earn you \(p_i\) 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 will earn \(p_2 = 10\) euros per day. After two days you will have earned \(20\) euros, exactly enough to pay off your friend (from whom you borrowed \(15\) euros) and retire with the remaining profits (\(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.
- The first line contains the number of investment options \(1 \leq n \leq 10^5\) and the minimum amount of money you need to retire \(1 \leq M \leq 10^9\).
- Then, \(n\) lines follow. Each line \(i\) has two integers: the daily profits of this investment \({1 \leq p_i \leq 10^9}\) and its initial cost \(1 \leq c_i \leq 10^9\).
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.
2 5
4 10
10 15
2
4 10
1 8
3 12
4 17
10 100
6
3 5
4 1
9 10
6 3
1