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

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

В сауне 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).

Выходные данные

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

Примеры

Примечание

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