Cho một dãy số nguyên gồm phần tử và một số nguyên .
Bạn được phép chọn ra một tập con các chỉ số . Gọi là số lượng phần tử của tập hợp . Điều kiện để tập hợp được coi là "hợp lệ" là trung bình cộng của các phần tử có chỉ số thuộc phải không nhỏ hơn . Nói cách khác:
Nhiệm vụ của bạn là tìm kích thước lớn nhất có thể của tập hợp .
Dữ liệu:
Dòng đầu tiên chứa số nguyên () — số lượng bộ dữ liệu (test cases).
Mỗi bộ dữ liệu gồm hai dòng:
Dòng thứ nhất chứa hai số nguyên và ().
Dòng thứ hai chứa số nguyên ().
Tổng giá trị của trên tất cả các bộ dữ liệu không vượt quá .
Kết quả:
Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là kích thước lớn nhất của tập hợp thỏa mãn yêu cầu.
Ví dụ:
Dữ liệu:
3
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
Kết quả:
2
4
0
Giải thích:
Ở ví dụ 1: Ta có thể chọn tập gồm các phần tử hoặc . Với , trung bình cộng là . Nếu chọn thêm bất kỳ phần tử nào khác, trung bình cộng sẽ nhỏ hơn 3.
Ở ví dụ 2: Tổng của 4 phần tử là . Trung bình cộng là . Vậy chọn cả 4 phần tử.
Ở ví dụ 3: Không có phần tử nào lớn hơn hoặc bằng 5, nên không thể chọn bất kỳ tập hợp nào (kể cả tập chỉ có 1 phần tử) để có trung bình cộng .
Giới hạn:
Subtask #1 (15% số điểm): Tổng trên tất cả các bộ dữ liệu không vượt quá .
Subtask #2 (25% số điểm): Tổng trên tất cả các bộ dữ liệu không vượt quá .
Subtask #3 (20% số điểm): Tổng và .
Subtask #4 (40% số điểm): Không có ràng buộc gì thêm.
