데이터 담기

Adam은 정리 정돈을 잘하는 사람으로, 자신의 모든 물건을 정리하는 데 늘 큰 관심을 보여 왔다. 특히 그는 젊은 시절 컴퓨터의 파일을 콤팩트 디스크로 옮기며 보낸 수많은 시간을 즐겁게 회상한다.

이 과정에는 매우 중요한 규칙이 두 가지 있었다. 첫째, 모든 디스크에 알아보기 쉬운 표지를 붙일 수 있도록 Adam은 같은 디스크에 파일을 두 개보다 많이 넣지 않았다. 둘째, 파일 하나를 여러 디스크에 나누어 넣지 않았다. 다행히 그가 사용한 디스크는 항상 이 규칙들을 지킬 수 있을 만큼 충분히 컸다.

과거를 돌이켜 보며, Adam은 이제 자신이 파일을 최선의 방법으로 배치했는지, 아니면 콤팩트 디스크를 낭비했는지 궁금해한다. 그는 자신이 사용한 디스크의 용량(모든 디스크의 용량은 같았다)과 저장한 파일들의 크기 목록을 제공할 것이다. 물론 매우 중요한 두 규칙을 따르면서 모든 파일을 저장하는 데 필요한 디스크의 최소 개수를 구하여 Adam을 도와주자.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ X ≤ 700. 1 ≤ $S_{i}$ ≤ X.

소규모 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 10.

대규모 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ $10^{4}$

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 저장할 파일의 수 N과 사용할 디스크의 용량 X(MBs)를 나타내는 두 정수가 포함된 줄로 시작한다. 다음 줄에는 파일들의 크기 $S_{i}$(MBs)를 나타내는 N개의 정수가 하나의 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며 (1부터 시작한다), y는 주어진 파일들을 저장하는 데 필요한 디스크의 최소 개수이다.