Venta de árboles de bambú
Tienes un solo árbol de bambú. Crece a diferentes velocidades según el día. Quieres ganar dinero cortándolo y vendiéndolo (el árbol seguirá creciendo incluso después de ser cortado).
El bambú comienza con una longitud de 0 el día 1 y crece a lo largo de
n días. Conoces el precio por cada metro de bambú en cada uno de los días y cuánto crece la noche antes de venderlo.
En cada día, puedes decidir si cortar todo el árbol (seguirá creciendo luego de cortarlo) y venderlo o dejarlo para que continúe creciendo. ¿Cuál es la cantidad máxima de dinero que puedes obtener?
Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ), que representa el número de días.Las siguientes
n líneas contienen dos enteros separados por espacio (, ) (1 ≤ , ≤ ). Aquí, es el número de metros que crecerá el árbol la noche anterior a la venta y es el precio por metro de bambú en el día i.Salida
El programa debe imprimir la cantidad máxima de dinero que puedes obtener al hacer crecer y vender el bambú. Se garantiza que la respuesta no excede .
Ejemplos
Entrada | Salida |
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