题目描述

现有 $N$ 套待售房屋。第 $i$ 套房屋的价格为 $A_i$ 美元。你拥有的预算为 $B$ 美元。

请问你最多能购买多少套房屋？

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $B$。第二行包含 $N$ 个整数，其中第 $i$ 个整数为 $A_i$，表示第 $i$ 套房屋的价格。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是你能购买的最大房屋数量。

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

提示

在样例 #1 中，你的预算为 $100$ 美元。你可以购买第 $1$ 套和第 $3$ 套房屋，花费 $20 + 40 = 60$ 美元。

在样例 #2 中，你的预算为 $50$ 美元。你可以购买第 $1$、$3$ 和第 $4$ 套房屋，花费 $30 + 10 + 10 = 50$ 美元。

在样例 #3 中，你的预算为 $300$ 美元。你无法购买任何房屋（因此答案为 $0$）。

限制条件

$1 \le T \le 100$。

$1 \le B \le 10^5$。

对于所有 $i$，$1 \le A_i \le 1000$。

测试集 1

$1 \le N \le 100$。

测试集 2

$1 \le N \le 10^5$。

翻译由 DeepSeek V4 Pro 完成