题目描述

我们准备建造一道非常长的栅栏。

现在，栅栏的位置已经确定，剩下的问题就是购买足够的建筑材料。附近的五金店出售若干种不同长度的木板，每种长度的木板都可以购买任意多块。

为了避免浪费，我们希望购买的所有木板长度之和恰好等于栅栏的总长度。

给定栅栏的长度以及可以购买的木板长度，请你求出：为了恰好拼出这道栅栏，最少需要购买多少块木板。

需要特别注意的是：这道栅栏非常非常长！

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来包含 $T$ 组测试数据，每组测试数据包含两行。

每组数据的第一行包含两个整数 $l$ 和 $n$，其中：

• $l$ 表示栅栏的总长度；
• $n$ 表示可以购买的不同木板长度的种数。

第二行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示所有可以购买的木板长度。

每种长度的木板都可以购买任意多块。

输出格式

对于每组测试数据，输出一行：

Case #x: M

其中 $x$ 表示测试数据编号，从 $1$ 开始。

$M$ 的含义如下：

• 如果可以购买一块或多块木板，使它们的总长度恰好等于 $l$，则 $M$ 为所需木板数量的最小值；
• 如果无法恰好拼出长度 $l$，则输出字符串 IMPOSSIBLE。

样例输入

2
10000000001 3
23 51 100
10000000001 3
100 52 22

样例输出

Case #1: 100000004
Case #2: IMPOSSIBLE

样例说明

对于第一组样例，一种最优方案为：

• 使用 $2$ 块长度为 $23$ 的木板；
• 使用 $5$ 块长度为 $51$ 的木板；
• 使用 $99999997$ 块长度为 $100$ 的木板。

总长度为

$2\times23+5\times51+99999997\times100=10000000001$。

共使用

$2+5+99999997=100000004$

块木板，因此答案为 $100000004$。

虽然也可以使用 $100000001$ 块长度为 $100$ 的木板，使总长度超过 $l$，但题目要求木板总长度必须恰好等于 $l$，因此这种方案是不允许的。

对于第二组样例，所有可购买的木板长度都是偶数，因此无论购买多少块木板，总长度都一定是偶数。而目标长度 $10000000001$ 是奇数，所以无法恰好拼出目标长度。

数据规模与约定

对于所有测试数据：

• $1\le T\le50$；
• $10^{10}\le l\le10^{18}$；
• $1\le n\le100$；
• 同一组测试数据中的所有 $b_i$ 两两不同。

小数据：

• $1\le b_i\le100$。

大数据：

• $1\le b_i\le10^5$。

子任务与评分

本题采用子任务计分，满分为 $100$ 分。

两个子任务独立计分。必须正确输出某个子任务内全部测试组的答案，才能获得该子任务的全部分数，否则该子任务得 $0$ 分。

原 Code Jam 比赛的 Small、Large 分别为 $7$ 分和 $22$ 分；本站保持满分 $100$ 分，将其按比例取整为 $24$ 分和 $76$ 分。两档均满足上面的所有公共约束。

题目来源

Round 3。

鸣谢成都七中 Zxytim。