Bạn là quản lý quan hệ công chúng của một hãng sản xuất sô-cô-la. Đáng tiếc, hình ảnh công ty bị tổn hại vì khách hàng cho rằng ông chủ keo kiệt và bủn xỉn. Bạn hy vọng xóa bỏ ấn tượng đó bằng cách tổ chức tham quan nhà máy và nếm sô-cô-la miễn phí.

Ngay sau khi bắt đầu dự án, bạn nhận ra tiếng xấu của ông chủ hoàn toàn có cơ sở: ông chỉ đồng ý tặng sô-cô-la nếu bạn giảm chi phí xuống thấp nhất. Sô-cô-la được đóng thành gói, mỗi gói có \(P\) miếng. Bạn muốn mở gói mới cho từng đoàn tham quan, nhưng ông chủ khăng khăng rằng nếu một đoàn dùng còn thừa, số miếng đó phải được dùng cho đoàn kế tiếp trước khi mở gói mới.

Ví dụ, mỗi gói có \(P=3\) miếng và một đoàn 5 người đến. Bạn mở hai gói để mỗi người nhận một miếng và còn thừa một miếng. Sau đó một đoàn 6 người đến: họ nhận miếng thừa trước, rồi bạn mở thêm hai gói để phát đủ, và lại thừa một miếng. Nếu tiếp theo là hai đoàn 4 người, đoàn đầu nhận miếng thừa cùng một gói nguyên; đoàn 4 người cuối nhận sô-cô-la từ hai gói mới mở. Bạn không được mở gói mới trước khi dùng hết đồ thừa, ngay cả khi định dùng hết gói mới lập tức.

Trong ví dụ đó, 2 trong 4 đoàn — đoàn đầu và đoàn cuối — nhận toàn bộ sô-cô-la từ các gói mới mở. Hai đoàn còn lại nhận cả sô-cô-la mới lẫn đồ thừa. Bạn biết phát đồ thừa không phải cách hay để sửa hình ảnh bủn xỉn của ông chủ, nhưng phải chấp nhận hệ thống này để ông sếp hà tiện đồng ý dự án. Dù hoàn cảnh bất lợi, bạn vẫn quyết tâm làm thật tốt.

Bạn có yêu cầu từ \(N\) đoàn; mỗi đoàn cho biết số người sẽ đến. Các đoàn vào nhà máy lần lượt. Bạn muốn chọn thứ tự sao cho nhiều đoàn nhất chỉ nhận sô-cô-la mới, không nhận đồ thừa. Không được từ chối đoàn nào, không được phát cho một đoàn nhiều hơn một lần và phải phát đúng một miếng cho mỗi người.

Với các đoàn ở ví dụ trên, nếu thứ tự là 4, 5, 6, 4 thay vì 5, 6, 4, 4 thì có 3 đoàn — tất cả trừ đoàn 5 người — chỉ nhận sô-cô-la mới. Không cách sắp nào cho cả bốn đoàn chỉ nhận sô-cô-la mới.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa \(N\), số đoàn tham quan, và \(P\), số miếng mỗi gói. Dòng thứ hai chứa \(N\) số nguyên \(G_1,G_2,\ldots,G_N\), số người trong từng đoàn.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số đoàn tối đa chỉ nhận sô-cô-la mới khi chọn thứ tự tốt nhất.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le G_i\le100\) với mọi \(i\).

Phân nhóm

Test Set 1 (Visible): \(2\le P\le3\).

Test Set 2 (Hidden): \(2\le P\le4\).

Đ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ụ

3
4 3
4 5 6 4
4 2
4 5 6 4
3 3
1 1 1

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

Nguồn

Google Code Jam 2017, Vòng 2, bài Fresh Chocolate.

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