Розподіл каменів#8646
У міському спорткомплексі є сучасна сауна, яка зігріває студентів у будь-яку пору року. Проте її технологічне оснащення настільки складне, що керівництво спорткомплексу не знає, як правильно її обслуговувати.
Сауна складається з n - 1 послідовно з'єднаних відділень. Між сусідніми відділеннями розташовані печей (по одній між кожними двома відділеннями, одна перед першим і одна після останнього).
Обсяг -го відділення дорівнює k_i, у кожну піч можна завантажити від до каменів. Якщо в -ій печі знаходиться p_i каменів, то в -е відділення надходить k_i \cdot p_i \cdot p_{i+1} джоулів тепла.
У спорткомплексу є каменів. Керівництво хоче мінімізувати загальну кількість тепла, що надходить у всі відділення сауни, щоб в інших частинах спорткомплексу не було надто спекотно, але при цьому використати всі камені, бо викидати їх шкода. Допоможіть розв'язати цю задачу.
У першому рядку знаходяться три цілі числа , і (2 \le n \le 1000, 1 \le v \le 10^5, s \le n \cdot v) - кількість печей, кількість каменів і місткість кожної печі, відповідно.
У другому рядку містяться n - 1 цілих чисел k_i - обсяг -го відділення (1 \le k_i \le 10^5).
Виведіть єдине число - мінімальну сумарну теплоту у всіх відділеннях.
Приклад 1
У прикладі правильна відповідь досягається, якщо в першу і четверту піч покласти по чотири камені, а в другу - два. Тоді теплота у всіх відділеннях, крім першого, буде дорівнювати нулю, а в першому - восьми.