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

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

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

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

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

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

Во второй строке содержатся n - 1 целых чисел ki - объем i-го отделения (1 ≤ ki ≤ 105).

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

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

Пояснение

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