程序设计能力实训

1184. 整齐打印 (print neatly)

单点时限: 2.0 sec

内存限制: 256 MB

考虑整齐打印问题,即在打印机上用等宽字符打印一段文本。输入文本为 $n$ 个单词的序列,单词长度分别为 $l_1, l_2, \cdots, l_n$ 个字符。我们希望将此段文本整齐打印在若干行上,每行最多 $M$ 个字符。“整齐”的标准是这样的:如果某行包含第 $i$ 到第 $j (i\leqslant j)$ 个单词,且单词间隔为一个空格符,则行尾的额外空格符数量为 $M-j+i- \sum_{k=i}^j l_k$,此值必须为非负的,否则一行内无法容纳这些单词。我们希望最小化所有行的(除最后一行外)额外空格数的立方之和。

输入格式

第一行一个数 $n,M(1\leqslant n \leqslant 10^4, 1\leqslant M \leqslant 10^4)$,表示需要打印单词数和每行最多能容纳的字符数。
接下来 $n$ 个数 $l_1,l_2,\dots,l_n(1\leqslant l_i \leqslant M)$。

输出格式

输出一个数表示除最后一行外额外空格数的立方之和的最小值。

样例

Input
5 5
5 5 1 2 2
Output
1
不限期开放

题目列表