텍스트 정렬

외계 지성체 ∀I¶אΞ℘가 당신을 조판 시스템 프로그래머로 고용했다. 오늘 할 일은 텍스트 정렬 알고리즘을 설계하는 것이다.

텍스트 정렬은 문단이라는 단어 열과 종이의 너비가 주어졌을 때, 적절한 위치에 줄바꿈을 넣어 각 줄의 너비를 최대한 균등하게 만드는 작업이다. 아직 자동 하이픈 삽입 알고리즘을 개발하지 않았으므로 단어 중간에서 줄을 바꿀 수 없다. 그리고 그들의 언어는 단어 사이에 공백을 넣지 않으므로 공백은 고려하지 않아도 된다.

하나의 배치(즉, 문단에 줄바꿈을 넣어 만든 줄의 집합)가 얼마나 잘 정렬되었는지 측정하기 위해 다음과 같이 비용을 정의했다.

• 문단의 총 비용은 각 줄의 비용의 합이다.
• 마지막 줄의 비용은 max(0, s - w)로 정의한다.
• 나머지 줄의 비용은 |s - w|로 주어진다.

여기서 s는 그 줄에 있는 단어들의 너비 합이고, w는 종이의 너비이다.

문단이 주어졌을 때 최소 비용의 배치를 계산하는 알고리즘을 설계하시오.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 양의 정수 n과 w가 주어진다(0 ≤ n ≤ 1000, 0 ≤ w ≤ 1,000,000). n은 문단의 길이이고 w는 사용하는 종이의 너비이다. 다음 n개 줄에는 각각 양의 정수 ai가 하나씩 주어지며, 이는 문단의 i번째 단어의 너비이다. 여기서 0 ≤ ai ≤ w가 보장된다.

입력은 두 개의 0이 있는 줄로 끝난다. 이 줄은 어떤 테스트 케이스에도 속하지 않으며 처리해서는 안 된다.

각 테스트 케이스마다 케이스 번호와 문단의 최소 비용을 출력한다.