Задача Bamboo
Фермер Василий чтобы поправить свои дела завез и начал выращивать сахарный тростник - растет быстро, затрат минимум, доходы большие, хотя сахар получается невкусный. Именно сейчас начался сезон роста тростника. Каждый день Василий срезает тростник. Заранее известно, сколько тростника Василий сможет срезать каждый день. Скупщики тростника принимают любое количество ежедневно ровно в полдень. Однако цена тростника каждый день меняется. Нам удалось узнать, по какой цене они будут принимать тростник. В любой день можно продать срезанный тростник: можно все, а можно часть имеющегося тростника (или весь) придержать для получения большей выручки. Однако, те побеги тростника, которые пролежали K суток (или более), теряют ценность, и скупщики их не берут. Нужно определить, какую максимальную выручку от продажи тростника можно получить. Сезон роста и скупки тростника начинается в полдень нулевого дня и длится ровно N суток.
Технические условия. Программа Bamboo читает с клавиатуры два натуральных числа N (1 <= N <= 150000) и K (1 <= K <= N), а далее N пар целых положительных чисел, на сколько метров вырос тростник за эти сутки и цена одного метра тростника в тот же день. Все сила разделены пробелами. Программа выводит на экран одно целое неотрицательное число - наибольший возможный доход от продажи тростника. Гарантируется, что результат не превышает 231-1.
|
Ввод |
Вывод |
Пояснение |
|
3 2 1 2 3 1 5 3 |
26 |
26=1*2+3*3+5*3 |
|
7 3 6 2 2 1 5 3 4 5 7 2 1 4 4 1 |
109 |
109=6*3+2*5+5*5+4*5+7*4+1*4+4*1 |