구매

판매 중인 집이 N채 있다. i번째 집을 사는 데는 $A_{i}$달러가 든다. 사용할 수 있는 예산은 B달러이다.

살 수 있는 집의 최대 개수는 얼마인가?

제한

시간 제한: 15초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ B ≤ $10^{5}$. 모든 i에 대해, 1 ≤ $A_{i}$ ≤ 1000.

테스트 세트 1

1 ≤ N ≤ 100.

테스트 세트 2

1 ≤ N ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 B가 포함된 한 줄로 시작한다. 두 번째 줄에는 N개의 정수가 주어진다. i번째 정수는 i번째 집의 가격인 $A_{i}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 살 수 있는 집의 최대 개수이다.

예제 케이스 #1에서는 예산이 100달러이다. 1st 집과 3rd 집을 20 + 40 = 60달러에 살 수 있다. 예제 케이스 #2에서는 예산이 50달러이다. 1st, 3rd, 4th 집을 30 + 10 + 10 = 50달러에 살 수 있다. 예제 케이스 #3에서는 예산이 300달러이다. 어떤 집도 살 수 없다(따라서 답은 0이다).

참고: 이전 대회와 달리 Kick Start 2020에서는 모든 테스트 세트가 결과가 공개되는 테스트 세트이므로, 제출 즉시 피드백을 받는다.