Là nhà giả kim giỏi nhất đất nước, bạn lại được triệu tập vì nhà lãnh đạo ngày càng tham lam các kim loại hiếm và cần đến sức mạnh vượt ngoài khoa học.

Mỗi kim loại được biểu diễn bởi một số nguyên dương. Bạn cần tạo \(U_1\) đơn vị kim loại \(1\), \(U_2\) đơn vị kim loại \(2\), ..., \(U_N\) đơn vị kim loại \(N\). Các kim loại \(N+1,N+2,\ldots\) vẫn tồn tại nhưng không có số lượng bắt buộc. Bạn có thể tạo dư bất kỳ kim loại nào rồi loại bỏ phần dư.

Do cắt giảm ngân sách, bạn chỉ còn một phép giả kim đơn giản. Với hai số cố định \(A<B\), có thể phá hủy một đơn vị kim loại \(i\) để tạo một đơn vị kim loại \(i-A\) và một đơn vị kim loại \(i-B\). Nếu một chỉ số không dương thì đơn vị tương ứng không được tạo. Cụ thể, nếu \(i\le A\), phép thuật chỉ phá hủy mà không tạo gì; nếu \(A<i\le B\), nó chỉ tạo một đơn vị kim loại \(i-A\).

Một thợ mỏ chuyên gia có thể mang về đúng một đơn vị của bất kỳ kim loại nào bạn yêu cầu. Từ đó, bạn dùng phép thuật lên kim loại ban đầu và các sản phẩm về sau để tạo thêm đơn vị. Hình dưới minh họa một đơn vị kim loại \(4\) tạo thành một đơn vị kim loại \(1\) và hai đơn vị kim loại \(2\) bằng hai phép thuật với \(A=1,B=2\).

Kim loại có chỉ số lớn nặng hơn và khó xử lý hơn. Hãy tìm chỉ số nhỏ nhất của một kim loại mà chỉ một đơn vị của nó đủ hoàn thành nhiệm vụ, hoặc cho biết không có kim loại như vậy.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ gồm hai dòng. Dòng đầu chứa \(N,A,B\): chỉ số kim loại lớn nhất bắt buộc tạo và hai tham số phép thuật. Dòng thứ hai chứa \(N\) số \(U_1,\ldots,U_N\), là số đơn vị yêu cầu của từng kim loại.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y. Nếu không thể tạo đủ từ một đơn vị duy nhất, \(y\) là IMPOSSIBLE; nếu có thể, \(y\) là chỉ số nhỏ nhất của kim loại khởi đầu đủ dùng.

Ràng buộc

• \(1\le T\le100\); \(1\le N\le20\).
• \(0\le U_i\le20\) với mọi \(i\); \(U_N\ge1\).
• \(2\le U_1+\cdots+U_N\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(A=1,B=2\).
• Test Set 2 (Hidden Verdict): \(1\le A<B\le20\).

Đ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
2 1 2
1 2
5 1 2
2 0 0 0 1
3 1 2
1 1 1

Case #1: 4
Case #2: 6
Case #3: 5

Ví dụ bổ sung — Test Set 2

??? "Giải thích"
    Ví dụ này thỏa Test Set 2 nhưng không được chạy trên lời giải nộp.

    !!! question "Ví dụ 2"
        ???+ "Input"
            ```sample
            3
            3 2 4
            1 1 1
            3 2 4
            1 0 1
            5 2 5
            1 0 0 0 1
            ```
        ???+ success "Output"
            ```sample
            Case #1: IMPOSSIBLE
            Case #2: 5
            Case #3: 10
            ```
        ??? "Giải thích"
            Với bộ đầu, không thể bắt đầu từ một đơn vị kim loại bất kỳ, lặp phép thuật $A=2,B=4$, rồi còn lại một đơn vị của mỗi kim loại $1,2,3$.

Nguồn

Google Code Jam 2021, Vòng 1B, bài Subtransmutation.

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