Armin đang chơi Osmos, một trò chơi giải đố dựa trên vật lý được phát triển bởi Hemisphere Games. Trong trò chơi này, anh ấy điều khiển một "mote" (hạt), di chuyển xung quanh và hấp thụ các hạt nhỏ hơn.

Trong trò chơi này, một hạt có thể hấp thụ (hoặc bị hấp thụ bởi) những thứ khác! Trò chơi trong bài toán này có ý tưởng tương tự như Osmos, nhưng không yêu cầu bạn phải từng chơi trò chơi này.

Khi hạt của Armin hấp thụ một hạt nhỏ hơn, hạt của anh ấy sẽ lớn thêm một lượng bằng kích thước của hạt nhỏ đó. Sau khi lớn hơn, anh ấy có thể hấp thụ thêm nhiều hạt hơn nữa.
Ví dụ: giả sử hạt của Armin có kích thước \(10\), và có các hạt khác với kích thước \(9, 13\) và \(19\). Ban đầu, hạt của Armin chỉ có thể hấp thụ hạt kích thước \(9\). Sau khi hấp thụ, nó sẽ có kích thước \(19\). Sau đó, nó có thể hấp thụ hạt kích thước \(13\). Khi đó, nó sẽ có kích thước \(32\). Bây giờ, hạt của Armin có thể hấp thụ hạt cuối cùng.

Lưu ý rằng hạt của Armin chỉ có thể hấp thụ một hạt khác nếu và chỉ nếu hạt đó nhỏ hơn. Nếu hạt khác có cùng kích thước, hạt của Armin không thể hấp thụ nó.

Bạn chịu trách nhiệm cho chương trình tạo ra các hạt để Armin hấp thụ. Chương trình đã tạo ra một số hạt với các kích thước khác nhau và hạt của Armin. Thật không may, với kích thước hạt của Armin và danh sách các hạt khác, có thể không có cách nào để Armin hấp thụ tất cả chúng.

Bạn muốn khắc phục điều đó. Có hai loại thao tác bạn có thể thực hiện, theo bất kỳ thứ tự nào, bất kỳ số lần nào: bạn có thể thêm một hạt có kích thước nguyên dương bất kỳ vào trò chơi, hoặc bạn có thể loại bỏ bất kỳ một hạt hiện có nào. Số lần tối thiểu bạn cần thực hiện các thao tác đó để Armin có thể hấp thụ mọi hạt khác là bao nhiêu?

Ví dụ, giả sử hạt của Armin có kích thước \(10\) và các hạt khác có kích thước \([9, 20, 25, 100]\). Trò chơi này hiện không thể giải được, nhưng bằng cách thêm một hạt kích thước \(3\) và loại bỏ hạt kích thước \(100\), bạn có thể làm cho nó giải được chỉ trong \(2\) thao tác. Đáp án ở đây là \(2\).

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Dòng đầu tiên của mỗi bộ thử nghiệm cho biết kích thước hạt của Armin, \(A\), và số lượng các hạt khác, \(N\). Dòng thứ hai chứa \(N\) kích thước của các hạt khác. Tất cả các kích thước hạt được cho sẽ là số nguyê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ố thao tác tối thiểu cần thiết để trò chơi có thể giải được.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Tập dữ liệu 1 (Small - Visible):
  • \(1 \le A \le 100\).
  • \(1 \le\) tất cả kích thước hạt \(\le 100\).
  • \(1 \le N \le 10\).
• Tập dữ liệu 2 (Large - Hidden):
  • \(1 \le A \le 10^6\).
  • \(1 \le\) tất cả kích thước hạt \(\le 10^6\).
  • \(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
2 2
2 1
2 4
2 1 1 6
10 4
25 20 9 100
1 4
1 1 1 1

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

Nguồn

Google Code Jam 2013, Vòng 1B, bài Osmos.

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