Venda de bambus
Dispõe de um único bambu. Ele cresce a velocidades diferentes em cada dia. Quer ganhar algum dinheiro cortando e vendendo o bambu (a planta continuará a crescer mesmo depois de ser cortada).
O bambu tem comprimento 0 no dia 1 e cresce ao longo de
n dias. Sabe qual é o preço de cada metro de bambu em cada um desses dias e também quanto ele cresce na noite anterior à venda.
Em cada dia, pode optar por cortar todo o bambu (que continuará a crescer após o corte) e vendê-lo, ou deixá-lo crescer mais. Qual é o valor máximo que pode obter?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ), o número de dias.As próximas
n linhas contêm dois inteiros separados por espaço (, ) (1 ≤ , ≤ ), que representam o número de metros que o bambu crescerá na noite anterior à venda e o preço de cada metro de bambu no dia i.Saída
O programa deve imprimir o montante máximo que pode ganhar fazendo o bambu crescer e vendendo-o. Está garantido que a resposta não excede .
Exemplos
Entrada | Saída |
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