Problems
Text Justi?cation
Text Justi?cation
You are hired by the \textbf{∀ℑ¶ℵΞρ}, an extraterrestrial intelligence, as a programmer of their typesetting system. Your task today is to design an algorithm for text \textit{justification}.
Text justification is to equalize the line widths as much as possible by inserting line breaks at appropriate positions, given a word sequence called a \textit{paragraph} and the width of the paper. Since you have not developed an automatic hyphenation algorithm yet, you cannot break a line in the middle of a word. And since their language does not put spaces between words, you do not need to consider about spacing.
To measure how well the text is justified in one configuration (i.e., a set of lines generated by inserting line breaks to a paragraph), you have defined its cost as follows:
\begin{itemize}
\item The total cost of a paragraph is the sum of the cost of each line.
\item The cost for the last line is defined as max(\textbf{0}, \textbf{s − w}).
\item The cost for other lines are given by \textbf{|s − w|}.
\end{itemize}
where \textbf{s} is the sum of the widths of the words in the line, and \textbf{w} is the width of the paper.
Please design the algorithm which takes a paragraph and calculates the configuration of the minimum cost.
\InputFile
The input consists of multiple test cases.
The first line of each test case contains two positive integers \textbf{n} and \textbf{w} (\textbf{0} ≤ \textbf{n} ≤ \textbf{1000} and \textbf{0} ≤ \textbf{w} ≤ \textbf{1000000}). \textbf{n} is the length of paragraph and \textbf{w} is the width of the used paper. Each of the following \textbf{n} lines contains one positive integer \textbf{a_i} which indicates the width of the \textbf{i}-th word in the paragraph. Here it is guaranteed that \textbf{0} ≤ \textbf{a_i} ≤ \textbf{w}.
The input terminates with the line containing two zeros. This is not a part of any test case and should not be processed.
\OutputFile
For each test case, print the case number and the minimum cost for the paragraph.