Vendre des bambous
Vous disposez d’un seul pied de bambou. Il pousse à des vitesses différentes selon les jours. Vous aimeriez gagner un peu d’argent en le coupant et en le vendant (la plante continue de pousser même après avoir été coupée).
Le bambou a initialement une longueur de 0 le premier jour et pousse sur
n jours. Vous savez combien coûte chaque mètre de bambou à chacun de ces jours, ainsi que de combien la plante va grandir la nuit précédant la vente.
Chaque jour, vous pouvez soit couper la totalité du bambou (en gardant à l’esprit qu’il continuera à pousser par la suite), soit le laisser pousser pour le vendre plus tard. Quel est le montant maximal que vous pouvez obtenir ?
Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ ) représentant le nombre de jours.Les
n lignes suivantes contiennent deux entiers séparés par un espace (, ) (1 ≤ , ≤ ), où est le nombre de mètres dont le bambou grandira la nuit précédant la vente, et est le prix d’un mètre de bambou le jour i.Sortie
Le programme doit afficher le montant maximal que vous pouvez gagner en faisant pousser et en vendant le bambou. On garantit que la réponse ne dépassera pas .
Exemples
Entrée | Sortie |
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