Pianificazione finanziaria#9883
Essendo un giovane responsabile, avete deciso di pensare in anticipo alla pensione. Facendo un rapido calcolo, avete scoperto che per vivere senza preoccupazioni in pensione vi serviranno almeno euro.
Al momento non avete un soldo, ma, fortunatamente, il vostro generoso amico multimiliardario vi ha proposto di prestarvi senza interessi tutti i soldi che vorrete per investirli nel mercato azionario. Dopo aver ottenuto il profitto, restituirete all'amico la somma presa in prestito, mentre il resto lo terrete per voi.
Avete a disposizione possibilità di investimento, la -esima delle quali costa c_i euro. Grazie alle vostre competenze informatiche, avete anche previsto che il -esimo investimento vi porterà p_i euro al giorno. In ogni possibilità si può investire al più una volta, ma è possibile investire in quante possibilità diverse si vuole. Qual è il numero minimo di giorni necessario per saldare il debito con l'amico e andare in pensione?
Consideriamo, ad esempio, il primo test. Se si acquista solo il secondo investimento (del costo di euro), esso porterà p_2 = 10 euro al giorno. Dopo due giorni guadagnerete euro — esattamente quanto basta per restituire all'amico i euro presi in prestito e andare in pensione con i restanti euro di profitto. Guadagnare un profitto netto di euro in un solo giorno è impossibile, quindi due giorni è la risposta migliore possibile.
Nella prima riga sono forniti il numero di possibilità di investimento n~(1 \le n \le 10^5) e la somma minima di denaro m~(1 \le m \le 10^9), necessaria per andare in pensione.
Ciascuna delle successive righe contiene due numeri interi: il profitto giornaliero p_i~(1 \le p_i \le 10^9) dell'-esimo investimento e il suo costo iniziale c_i~(1 \le c_i \le 10^9).
Stampate il numero minimo di giorni necessario per saldare il debito con l'amico e andare in pensione avendo almeno euro, con la strategia di investimento ottimale.
Esempio 1
Esempio 2
Esempio 3