Problem

Có \(N\) ngôi nhà đang được bán. Ngôi nhà thứ \(i\) có giá \(A_i\) đô-la để mua. Bạn có \(B\) đô-la để chi tiêu.

Số nhà tối đa mà bạn có thể mua là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên của đầu vào cho biết số lượng của các testcase, \(T\). Dưới đây là \(T\) testcase. Mỗi testcase bắt đầu bằng một đòng duy nhất chứa hai số nguyên \(N\) và \(B\).
• Dòng thứ hai chứa số nguyên \(N\). Số nguyên thứ \(i\) là \(A_i\), chi phí của ngôi nhà thứ \(i\).

Dữ liệu ra

• Với mỗi testcase, in ra một dòng chứa Case #x: y, mà x là số lượng testcase (bắt đầu từ 1) và y là số nhà tối đa mà bạn có thể mua.

Giới hạn

• Thời gian: 15 giây.
• Bộ nhớ: 1 GB.
• \(1 \le T \le 100\).
• \(1 \le B \le 10^{5}\).
• \(1 \le A_i \le 1000\), cho tất cả \(i\).
• Test Set 1: \(1 \le N \le 100\)
• Test Set 2: \(1 \le N \le 10^{5}\)

Sample

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

Nguồn

Google Kickstart 2020, vòng A, bài Allocation
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.