Задача №112528. Быстро растет бамбук...
Скоро начнётся сезон роста бамбука. Скупщики бамбука принимают любое количество бамбука каждый день ровно в полдень. Однако цена бамбука каждый день меняется. Нам удалось узнать, по какой цене скупщики будут принимать бамбук. Кроме того, мы точно знаем, на сколько метров вырастает бамбук за каждые сутки (эта величина тоже меняется). В любой день можно либо срезать весь бамбук целиком и продать его, либо оставить бамбук расти дальше. После срезания бамбук продолжает расти. Требуется определить, какую максимальную прибыль от продажи бамбука можно получить. В полдень нулевого дня (начало сезона роста бамбука) длина бамбука равна 0. Сезон роста бамбука длится ровно N суток.
В первой строке входного файла находится натуральное число N , 1 ≤ N ≤ 100000 . В каждой из следующих N строк содержатся два целых положительных числа, разделенных пробелом: цена одного метра бамбука в определенный день и на сколько метров вырос бамбук за последние сутки. В ( i + 1) - й строке файла содержатся данные, относящиеся к полудню i – го дня.
В единственной строке выходного файла следует выводить одно целое неотрицательное число – наибольшая возможная выручка от продажи бамбука. Гарантируется, что результат не превосходит 2 63 - 1 .
8 2 7 4 1 3 3 5 5 2 4 5 2 4 7 1 1
139