Text Justi?cation

You are hired by the ∀ℑ¶ℵΞρ, 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 positions, 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.

Input

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 ≤ 1000000). 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 i-th word in the paragraph. Here it is guaranteed that 0 ≤ a_i ≤ w.

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

Output

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