Продажа бамбуковых деревьев
У вас есть одно бамбуковое дерево. Каждый день оно растёт с разной скоростью. Вы хотите заработать, срезая и продавая это дерево (оно по-прежнему продолжит расти, даже после срезания).
В первый день длина бамбука равна 0, и он растёт на протяжении
n дней. Вы знаете, сколько стоит каждый метр бамбука в разные дни и насколько дерево подрастёт в ночь перед продажей.
Каждый день вы можете полностью срезать дерево (после этого оно продолжит расти в следующие дни) и продать его либо оставить его расти дальше. Нужно определить, какую максимальную сумму можно заработать.
Входные данные
Первая строка содержит целое число
n (1 ≤ n ≤ ) — количество дней.Следующие
n строк содержат по два целых числа, разделённые пробелом: (, ) (1 ≤ , ≤ ). Первое число — сколько метров вырастет дерево в ночь перед продажей, второе — цена одного метра бамбука в день i.Выходные данные
Программа должна вывести максимально возможную сумму, которую можно заработать, выращивая и продавая бамбук. Гарантируется, что ответ не превысит .
Примеры
Входные данные | Выходные данные |
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