Chúng ta đang lên kế hoạch xây dựng một hàng rào rất dài. Chúng ta đã tìm được một địa điểm lý tưởng để xây dựng, và việc còn lại là thu thập vật liệu.

Từ các cửa hàng vật liệu xây dựng tại địa phương, chúng ta có thể mua số lượng không giới hạn các tấm ván gỗ, mỗi tấm có thể có nhiều độ dài khác nhau. Để tránh lãng phí, chúng ta muốn đảm bảo rằng tổng độ dài của các tấm ván này chính xác bằng độ dài của hàng rào mà chúng ta định xây dựng.

Cho biết độ dài của hàng rào và các độ dài tấm ván có thể sử dụng, số lượng tấm ván tối thiểu cần mua để có được độ dài chính xác là bao nhiêu?

Lưu ý: hàng rào sẽ rất dài!

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, T. T bộ test tiếp theo sẽ được đưa ra.

Mỗi bộ test gồm hai dòng. Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách L và N. Chúng đại diện cho tổng độ dài của hàng rào và số lượng các độ dài tấm ván khác nhau có thể mua. Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách B₁, B₂, ..., Bₙ, đại diện cho tất cả các độ dài tấm ván có thể có.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: M", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và M được xác định như sau:

• Nếu có thể mua một hoặc nhiều tấm ván sao cho tổng độ dài của chúng chính xác bằng L, thì M là số lượng tấm ván tối thiểu cần thiết để thực hiện việc này.
• Ngược lại, M là chuỗi "IMPOSSIBLE".

Ràng buộc

• 1 ≤ T ≤ 50.
• 10¹⁰ ≤ L ≤ 10¹⁸.
• 1 ≤ N ≤ 100.

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): 1 ≤ Bᵢ ≤ 100.
• Tập dữ liệu lớn (Test set 2 - Hidden): 1 ≤ Bᵢ ≤ 100000.

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

2
10000000001 3
23 51 100
10000000001 3
100 52 22

Case #1: 100000004
Case #2: IMPOSSIBLE

Nguồn

Google Code Jam 2010, Vòng 3, bài Fence.

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