신선한 초콜릿

당신은 초콜릿 제조업체의 홍보 관리자이다. 안타깝게도 고객들이 회사의 소유주가 인색하고 구두쇠라고 생각하기 때문에 회사의 이미지가 나빠졌다. 당신은 무료 공장 견학과 초콜릿 시식을 제공하여 그 인상을 없애고자 한다.

새 프로젝트를 시작한 직후, 회사 소유주의 평판에 그럴 만한 이유가 있다는 것을 깨달았다. 그는 당신이 비용을 최소화한다는 조건에서만 초콜릿을 무료로 나눠 주는 데 동의했다. 나눠 줄 초콜릿은 한 팩에 P조각씩 들어 있다. 당신은 각 견학 단체마다 새 팩을 열고 싶지만, 소유주는 한 단체에 주고 남은 조각이 있다면 새 팩을 열기 전에 반드시 다음 견학 단체에게 먼저 사용해야 한다고 주장한다.

예를 들어 각 팩에 P=3조각이 들어 있고, 5명의 견학 단체가 온다고 하자. 각 사람에게 한 조각씩 주기 위해 팩 두 개를 열면 한 조각이 남는다. 그 후에 6명의 다른 견학 단체가 온다고 하자. 이들은 남은 조각을 받은 다음, 시식용 초콜릿을 모두 나눠 주기 위해 팩 두 개를 더 열고, 그러면 다시 한 조각이 남는다. 바로 뒤이어 각각 4명인 단체 두 개가 온다면, 그중 첫 단체는 남은 조각과 온전한 팩 하나를 받고, 마지막 4명 단체는 새로 연 팩 두 개에서 초콜릿 조각을 받는다. 새로 연 팩을 곧바로 전부 사용할 계획이더라도 남은 조각을 모두 소진하기 전에는 새 팩을 열 수 없다는 점에 유의한다.

위 예제에서는 4개 단체 중 2개 단체(첫 단체와 마지막 단체)가 갓 연 팩에서만 초콜릿을 받았다. 나머지 2개 단체는 갓 연 초콜릿과 남은 초콜릿을 일부씩 받았다. 남은 초콜릿을 나눠 주는 것이 소유주의 인색한 이미지를 없애는 최선의 방법이 아니라는 것은 알지만, 인색한 상사가 프로젝트에 동의하게 하려면 이 방식을 받아들여야 했다. 불리한 상황에도 불구하고 당신은 일을 잘 해내기로 다짐했다.

N개 단체로부터 요청을 받았으며, 각 단체는 공장에 올 사람의 수를 명시했다. 단체들은 한 번에 하나씩 온다. 남은 초콜릿 없이 신선한 초콜릿만 받는 단체의 수가 최대가 되도록 이들을 들여보낼 순서를 정하고자 한다. 단체를 거절할 수도, 한 단체가 초콜릿을 두 번 이상 받을 수도 없으며, 각 단체의 각 사람에게 정확히 한 조각씩 주어야 한다.

위 예제에서 5, 6, 4, 4 대신 순서가 4, 5, 6, 4라면, 총 3개 단체(5명인 단체를 제외한 모든 단체)가 신선한 초콜릿만 받게 된다. 그 단체들의 집합에서는 어떤 배열로도 모든 단체가 신선한 초콜릿만 받게 할 수 없으므로, 이보다 더 잘할 수 없다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ 100. 모든 i에 대해 1 ≤ $G_{i}$ ≤ 100.

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 20초. 2 ≤ P ≤ 3.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 40초. 2 ≤ P ≤ 4.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 견학하러 오는 단체의 수 N과 팩당 초콜릿 조각 수 P를 나타내는 두 정수 N과 P가 주어진다. 둘째 줄에는 각 단체의 사람 수를 나타내는 N개의 정수 $G_{1}$, $G_{2}$, ..., $G_{N}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 그 수를 최대화하는 순서로 단체들을 들여보냈을 때 신선한 초콜릿만 받게 될 단체의 수이다.

예제 케이스 #1는 문제 설명에서 다룬 경우이다. 위에서 제시한 가능한 최적 순서 외에도 6, 5, 4, 4 같은 다른 순서 역시 신선한 초콜릿만 받는 단체의 수를 최대화하지만, 신선한 초콜릿을 받는 단체가 반드시 같지는 않다. 우리는 최고의 경험을 하는 단체의 사람 수 합계가 아니라 그러한 단체의 수에만 관심이 있다는 점에 유의한다.

예제 케이스 #2의 단체들은 케이스 #1와 같지만, 각 팩에는 초콜릿이 두 조각씩 들어 있다. 이 경우에는 예를 들어 4, 4, 6, 5와 같은 여러 순서로 모든 단체가 신선한 초콜릿만 받게 할 수 있다.

예제 케이스 #3에서는 모든 단체가 한 명으로만 이루어져 있으며, 모두 같은 팩에서 초콜릿을 먹게 된다. 물론 가장 먼저 들어오는 단체만 갓 연 팩에서 초콜릿을 받게 된다.