Задача 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 |