배분

면접 대비

시간 제한15초메모리 제한1024 MB

요약

집 가격 목록과 예산 B가 주어질 때, 예산을 넘지 않고 살 수 있는 집의 최대 개수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

매물로 나온 집이 $N$ 채 있다. $i$ 번째 집의 가격은 $A_i$ 달러다. 사용할 수 있는 예산은 $B$ 달러다.

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

입력

입력의 첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $N$ 과 $B$ 가 적힌 한 줄로 시작한다. 두 번째 줄에는 $N$ 개의 정수가 주어지며, $i$ 번째 정수는 $i$ 번째 집의 가격 $A_i$ 이다.

출력

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

제한

$1 \le T \le 100$ .
$1 \le B \le 105$ .
모든 $i$ 에 대해 $1 \le A_i \le 1000$ .

힌트

예제 케이스 #1에서 예산은 100달러다. 1번과 3번 집을 20 + 40 = 60달러에 살 수 있다.

예제 케이스 #2에서 예산은 50달러다. 1번, 3번, 4번 집을 30 + 10 + 10 = 50달러에 살 수 있다.

예제 케이스 #3에서 예산은 300달러다. 어떤 집도 살 수 없다 (답은 0).

예제1

예제 1

입력

3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999

예상 출력

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