Verkauf von Bambusbäumen
Du hast einen Bambusbaum, der an verschiedenen Tagen unterschiedlich schnell wächst. Du möchtest Geld verdienen, indem du ihn abschneidest und verkaufst (der Baum wächst auch nach dem Abschneiden weiter).
Am ersten Tag ist der Bambus 0 Meter lang und wächst insgesamt
n Tage. Du kennst sowohl den Preis pro Meter Bambus an jedem Tag als auch das Wachstum über Nacht, bevor du verkaufst.
An jedem Tag kannst du den ganzen Baum abschneiden (er wächst danach trotzdem weiter) und verkaufen oder ihn ungeschnitten lassen, damit er weiterwächst. Wie viel Geld kannst du auf diese Weise maximal verdienen?
Eingabe
Die erste Zeile der Eingabe enthält die ganze Zahl
n (1 ≤ n ≤ ), die Anzahl der Tage.Die nächsten
n Zeilen enthalten jeweils zwei durch Leerzeichen getrennte ganze Zahlen (, ) (1 ≤ , ≤ ). Dabei beschreibt um wie viele Meter der Baum in der Nacht vor dem Verkaufstag wächst, und ist der Preis pro Meter Bambus am Tag i.Ausgabe
Das Programm soll den maximalen Geldbetrag ausgeben, den du durch Wachsenlassen und Verkaufen des Bambus erzielen kannst. Es ist garantiert, dass das Ergebnis nicht überschreitet.
Beispiele
Eingabe | Ausgabe |
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