Finansal Planlama#9883
Sorumlu bir genç olarak, emekliliğinizle önceden ilgilenmeye karar verdiniz. Hızlıca bir hesap yaparak, emeklilikte rahat bir yaşam sürebilmek için en az avroya ihtiyacınız olduğunu belirlediniz.
Şu anda hiç paranız yok, ancak neyse ki milyarder bir arkadaşınız size borsaya yatırmanız için faizsiz olarak istediğiniz kadar para ödünç vermeyi teklif etti. Kâr elde ettikten sonra, arkadaşınıza ödünç aldığınız miktarı geri ödeyecek, kalanını ise kendinize saklayacaksınız.
Elinizde yatırım fırsatı bulunmaktadır; -inci fırsatın maliyeti c_i avrodur. Bilgisayar bilimindeki becerilerinizi kullanarak, -inci yatırımın size günde p_i avro kazandıracağını da tahmin ettiniz. Her fırsata en fazla bir kez yatırım yapılabilir, ancak istediğiniz kadar farklı fırsata yatırım yapabilirsiniz. Arkadaşınıza borcunuzu ödeyip emekli olabilmeniz için en az kaç gün gerekir?
Örneğin ilk testi ele alalım. Yalnızca ikinci yatırımı (maliyeti avro) satın alırsanız, bu yatırım günde p_2 = 10 avro kazandıracaktır. İki gün sonra avro kazanmış olursunuz — bu da tam olarak arkadaşınıza ödünç aldığınız avroyu geri ödeyip, kalan avro kârla emekli olmanız için yeterlidir. Bir günde net avro kâr elde etmek mümkün değildir, bu yüzden iki gün mümkün olan en iyi cevaptır.
İlk satırda yatırım fırsatlarının sayısı n~(1 \le n \le 10^5) ve emekli olmak için gereken minimum para miktarı m~(1 \le m \le 10^9) verilmiştir.
Sonraki satırın her biri iki tam sayı içerir: -inci yatırımın günlük kârı p_i~(1 \le p_i \le 10^9) ve başlangıç maliyeti c_i~(1 \le c_i \le 10^9).
Optimal yatırım stratejisiyle, arkadaşınıza borcunuzu ödeyip en az avroyla emekli olabilmeniz için gereken minimum gün sayısını yazdırın.
Örnek 1
Örnek 2
Örnek 3