Задача A. Разбиение абзаца на строки

Автор:Т. Кормен, Ч. Лейзерсон, Р. Ривест, Т. Чистяков   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Абзац текста состоит из n слов длиной l1, l2, ..., ln (длина слова - число символов в нем). Требуется оптимальным образом разбить его на строки длиной не более M символов. Оптимальность при этом определяется так: посчитаем число "лишних" пробелов в каждой строке и сложим кубы этих чисел для всех строк, кроме последней. Чем больше эта сумма (назовем ее оценочной суммой), тем хуже абзац.

Формат входного файла

В первой строке находятся числа n и M. Далее следует n чисел li.

Формат выходного файла

Выходной файл должен содержать единственное число - значение оценочной суммы абзаца при оптимальном разбиении на строки.

Ограничения

1 <= n <= 10000, 1 <= M <= 100000, 1 <= li <= M

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 6 
2 1 2 5
72

0.057s 0.010s 13