Розподіл каменів
У спорткомплексі Іннополіса є сучасна сауна, яка зігріває студентів у будь-яку пору року. Проте її технологічне оснащення настільки складне, що керівництво спорткомплексу не знає, як правильно її обслуговувати.
Сауна складається з n - 1 послідовно з'єднаних відділень. Між сусідніми відділеннями розташовані n печей (по одній між кожними двома відділеннями, одна перед першим і одна після останнього).
Обсяг i-го відділення дорівнює k[i]
, у кожну піч можна завантажити від 0 до v каменів. Якщо в i-ій печі знаходиться p[i]
каменів, то в i-е відділення надходить k[i]
* p[i]
* p[i+1]
джоулів тепла.
У спорткомплексу є s каменів. Керівництво хоче мінімізувати загальну кількість тепла, що надходить у всі відділення сауни, щоб в інших частинах спорткомплексу не було надто спекотно, але при цьому використати всі камені, бо викидати їх шкода. Допоможіть розв'язати цю задачу.
Вхідні дані
У першому рядку знаходяться три цілі числа n, s і v (2 ≤ n ≤ 1000, 1 ≤ v ≤ 10^5
, s ≤ n * v) - кількість печей, кількість каменів і місткість кожної печі, відповідно.
У другому рядку містяться n - 1 цілих чисел k[i]
- обсяг i-го відділення (1 ≤ k[i]
≤ 10^5
).
Вихідні дані
Виведіть єдине число - мінімальну сумарну теплоту у всіх відділеннях.
Приклади
Примітка
У прикладі правильна відповідь досягається, якщо в першу і четверту піч покласти по чотири камені, а в другу - два. Тоді теплота у всіх відділеннях, крім першого, буде дорівнювати нулю, а в першому - восьми.