Adam, một người đàn ông ngăn nắp, luôn quan tâm sâu sắc đến việc sắp xếp đồ đạc của mình. Đặc biệt, anh nhớ lại nhiều giờ thời trẻ đã dành để chuyển các tệp tin từ máy tính sang đĩa Compact (CD).

Có hai quy tắc rất quan trọng trong thủ tục này. Thứ nhất, để đảm bảo tất cả các đĩa có thể được dán nhãn rõ ràng, Adam sẽ không bao giờ đặt quá hai tệp tin trên cùng một đĩa. Thứ hai, anh sẽ không bao giờ chia một tệp tin duy nhất sang nhiều đĩa. May mắn thay, các đĩa anh sử dụng luôn đủ lớn để thực hiện điều này.

Nhìn lại, Adam hiện đang tự hỏi liệu mình đã sắp xếp các tệp tin theo cách tốt nhất hay chưa, hay liệu anh đã lãng phí một số đĩa Compact. Anh ấy sẽ cung cấp cho bạn dung lượng của các đĩa anh ấy đã sử dụng (tất cả các đĩa của anh ấy đều có cùng dung lượng) cũng như danh sách kích thước của các tệp tin mà anh ấy đã lưu trữ. Hãy giúp Adam bằng cách xác định số lượng đĩa tối thiểu cần thiết để lưu trữ tất cả các tệp tin của anh ấy — tất nhiên là tuân theo hai quy tắc rất quan trọng nêu trên.

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 bắt đầu bằng một dòng chứa hai số nguyên: số lượng tệp tin cần lưu trữ N, và dung lượng của các đĩa được sử dụng X (tính bằng MB). Dòng tiếp theo chứa N số nguyên đại diện cho kích thước của các tệp tin \(S_i\) (tính bằng MB), cách nhau bởi các khoảng trắng đơn.

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 đĩa tối thiểu cần thiết để lưu trữ các tệp tin đã cho.

Ràng buộc

• 1 ≤ T ≤ 100.
• 1 ≤ X ≤ 700.
• 1 ≤ \(S_i\) ≤ X.

Phân nhóm

• Small dataset: 1 ≤ N ≤ 10.
• Large dataset: 1 ≤ N ≤ 10⁴.

Đ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
3 100
10 20 70
4 100
30 40 60 70
5 100
10 20 30 40 60

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

Nguồn

Google Code Jam 2014, Vòng 2, bài Data Packing.

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