Bạn đang xem một chương trình nơi các Googler (nhân viên của Google) nhảy múa, và sau đó mỗi vũ công được ba giám khảo cho một bộ ba điểm số. Mỗi bộ ba điểm số gồm ba điểm số nguyên từ 0 đến 10. Các giám khảo có tiêu chuẩn rất giống nhau, vì vậy sẽ là bất ngờ nếu một bộ ba điểm số có hai điểm số cách nhau 2 đơn vị. Không có bộ ba điểm số nào chứa các điểm số cách nhau quá 2 đơn vị.

Ví dụ: (8, 8, 😎 và (7, 8, 7) không bất ngờ. (6, 7, 😎 và (6, 8, 😎 là bất ngờ. (7, 6, 9) sẽ không bao giờ xảy ra.

Tổng điểm của một Googler là tổng của ba điểm số trong bộ ba điểm số của Googler đó. Kết quả tốt nhất của một Googler là điểm số lớn nhất trong bộ ba điểm số của Googler đó. Cho biết tổng điểm của mỗi Googler, cũng như số lượng bộ ba điểm số bất ngờ, số lượng tối đa các Googler có thể có kết quả tốt nhất ít nhất là p là bao nhiêu?

Ví dụ, giả sử có 6 Googler và họ có tổng điểm như sau:
29, 20, 8, 18, 18, 21. Bạn nhớ rằng có 2 bộ ba điểm số bất ngờ, và bạn muốn biết có bao nhiêu Googler có thể đạt được kết quả tốt nhất từ 8 trở lên.

Với những tổng điểm đó, và biết rằng hai trong số các bộ ba là bất ngờ, các bộ ba điểm số có thể là:

10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)

Các trường hợp được đánh dấu (*) là các trường hợp bất ngờ. Điều này cho chúng ta 3 Googler đạt được ít nhất một điểm số từ 8 trở lên. Không có chuỗi bộ ba điểm số nào cho kết quả cao hơn 3, vì vậy câu trả lời là 3.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bao gồm một dòng duy nhất chứa các số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên là N, số lượng Googler, và số nguyên thứ hai là S, số lượng bộ ba điểm số bất ngờ. Số nguyên thứ ba là p, như đã mô tả ở trên. Tiếp theo là N số nguyên \(t_i\): tổng điểm của các Googler.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng tối đa Googler có thể có kết quả tốt nhất lớn hơn hoặc bằng p.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le S \le N\).
• \(0 \le p \le 10\).
• \(0 \le t_i \le 30\).
• Ít nhất S giá trị của \(t_i\) sẽ nằm trong khoảng từ 2 đến 28, bao gồm cả hai đầu.

Phân nhóm

• Tập kiểm tra 1 (Visible): \(1 \le N \le 3\).
• Tập kiểm tra 2 (Hidden): \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21

Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3

Nguồn

Google Code Jam 2012, Vòng loại, bài Dancing With the Googlers.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.