You are hired by the ĶI÷?¬?, an extraterrestrial intelligence, as a programmer of their typesetting system. Your
task today is to design an algorithm for *text justification*.

Text justification is to equalize the line widths as much as possible by inserting line breaks at appropriate posi-
tions, given a word sequence called a *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:

- The total cost of a paragraph is the sum of the cost of each line.
- The cost for the last line is defined as max(0,
*s*-*w*). - The cost for other lines are given by |
*s*-*w*|.

where *s* is the sum of the widths of the words in the line, and *w* is the width of the paper.

Please design the algorithm which takes a paragraph and calculates the configuration of the minimum cost.

The input consists of multiple test cases.

The first line of each test case contains two positive integers *n* and *w* (0 ≤ *n* ≤ 1000 and 0 ≤ *w* ≤ 1,000,000). *n*
is the length of paragraph and *w* is the width of the used paper. Each of the following n lines contains one positive
integer *a _{i}* which indicates the width of the

The input terminates with the line containing two zeros. This is not a part of any test case and should not be processed.

For each test case, print the case number and the minimum cost for the paragraph.

4 10 8 6 9 1 4 7 1 2 3 4 0 0

Case 1: 4 Case 2: 1

Source: ACM-ICPC Japan Alumni Group Practice Contest
, for World Finals, Tokyo, Japan, 2008-02-24

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/