Vendita di alberi di bambù
Hai un albero di bambù. Cresce a velocità diverse a seconda del giorno. Vuoi guadagnare un po’ di soldi tagliandolo e vendendolo (l’albero continuerà comunque a crescere dopo il taglio).
Il bambù ha una lunghezza di 0 il giorno 1 e cresce per
n giorni. Sai già quanto costa al metro in ciascuno di questi giorni e di quanto cresce ogni notte prima di venderlo.
Ogni giorno puoi decidere se tagliare completamente l’albero (che riprende comunque a crescere anche dopo essere stato tagliato) e venderlo, oppure se lasciarlo crescere ancora. Qual è l’importo massimo che puoi guadagnare?
Dati in input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ ), che rappresenta il numero di giorni.Le successive
n righe contengono due interi separati da uno spazio (, ), dove (1 ≤ , ≤ ). indica il numero di metri di crescita durante la notte precedente il giorno di vendita, mentre è il prezzo di un metro di bambù il giorno i.Dati in output
Il programma deve stampare il massimo importo che si può ottenere coltivando e vendendo il bambù. È garantito che il risultato non superi .
Esempi
Ingresso | Uscita |
8
7 2
1 4
3 3
5 5
4 2
2 5
7 4
1 1 | 139 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB