eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Распределение камней

Распределение камней

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

В спорткомплексе Иннополиса расположена сауна нового поколения, согревающая студентов в любое время года. Правда, её технологическое оснащение настолько продвинуто, что руководство спорткомплекса не знает, как обслуживать её надлежащим образом.

В сауне n - 1 последовательно соединённых отделений. Между соседними отделениями расположены n печей (по одной между каждыми двумя, одна перед первым и одна после последнего).

Объем i-го отделения равен k[i], в каждую печь можно загрузить от 0 до v камней. Пусть в i-ой печи находится p[i] камней, тогда в i-ое отделение поступает k[i] * p[i] * p[i+1] джоулей тепла.

В распоряжении спорткомплекса имеются s камней. Руководство желает минимизировать суммарную теплоту, поступающую во все отделения сауны, чтобы в остальной части спорткомплекса не было слишком жарко, но при этом использовать все камни, потому что выбрасывать их жалко. Решите эту задачу.

Вхідні дані

В первой строке находятся три целых числа n, s и v (2n1000, 1v10^5, sn * v) - количество печей, камней и вместимость каждой печи, соответственно.

Во второй строке содержатся n - 1 целых чисел k[i] - объем i-го отделения (1k[i]10^5).

Вихідні дані

Выведите единственное число - минимальную суммарную теплоту во всех отделениях.

Приклад

Вхідні дані #1
4 10 4
1 2 3
Вихідні дані #1
8

Примітка

В примере правильный ответ достигается, если в первую и четвёртую печь положить по четыре камня, а во вторую - два. Тогда теплота во всех отделениях, кроме первого, будет равна нулю, а в первом - восьми.

Джерело 2018 Інополіс Перший тур, 1 грудня