Text Justification

The extraterrestrial intelligence ∀I¶אΞ℘ has hired you as a programmer of its typesetting system. Your task today is to design an algorithm for text justification.

Text justification is the task of equalizing line widths as much as possible by inserting line breaks at appropriate positions, given a sequence of words called a paragraph and the width of the paper. No automatic hyphenation algorithm has been developed yet, so you cannot break a line in the middle of a word. And since their language puts no spaces between words, you do not need to consider spacing.

To measure how well the text is justified in one configuration (that is, a set of lines produced by inserting line breaks into a paragraph), the cost is defined as follows.

• The total cost of a paragraph is the sum of the cost of each line.
• The cost of the last line is max(0, s - w).
• The cost of the other lines is |s - w|.

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

Design an algorithm that takes a paragraph and computes the configuration of 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, 0 ≤ w ≤ 1,000,000). n is the length of the paragraph and w is the width of the paper used. Each of the following n lines contains one positive integer ai, the width of the i-th word in the paragraph. It is guaranteed that 0 ≤ ai ≤ w.

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

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