데이터 담기

면접 대비

시간 제한5초메모리 제한512 MB

요약

합이 디스크 용량을 넘지 않도록 파일을 최대 두 개씩 묶어 디스크 수를 최소화합니다.

문제

애덤은 무엇이든 정리해 두는 사람이다. 십 대 시절에 컴퓨터에 있던 파일을 CD로 옮기며 보낸 시간도 잘 기억한다.

옮길 때 지킨 규칙이 두 가지 있었다. 첫째, 모든 CD에 라벨을 또렷하게 붙이려고 한 장에 파일을 세 개 이상 담지 않았다. 둘째, 파일 하나를 여러 장에 나눠 담지 않았다. 애덤이 쓰던 CD는 언제나 그렇게 담을 만큼 넉넉했다.

지금 애덤은 그때 파일을 가장 알뜰하게 나눠 담았는지, 아니면 CD를 낭비했는지 궁금하다. 애덤이 쓴 CD의 용량과 저장한 파일의 크기 목록이 주어진다. CD의 용량은 모두 같다. 두 규칙을 지키면서 모든 파일을 담는 데 필요한 CD의 최소 개수를 구하여라.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 테스트 케이스가 $T$ 개 주어진다.

각 테스트 케이스의 첫 줄에는 파일의 개수 $N$ 과 CD 한 장의 용량 $X$ 가 정수 두 개로 주어진다. 용량의 단위는 MB이다. 다음 줄에는 파일 $N$ 개의 크기 $S_i$ 가 공백 하나로 구분되어 주어진다. 크기의 단위도 MB이다.

제한

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 모든 파일을 담는 데 필요한 CD의 최소 개수이다.

예제 1

입력

3
3 100
10 20 70
4 100
30 40 60 70
5 100
10 20 30 40 60

예상 출력

Case #1: 2
Case #2: 2
Case #3: 3

예제 3

입력

2
4 700
700 700 700 700
6 700
350 350 350 351 349 700

예상 출력

Case #1: 4
Case #2: 4