[Google Codejam2010]Fence

我们计划建造一道非常长的栅栏。目前，建造地点已经确定，接下来需要购买所需的木板。

当地的商店提供长度各异的木板，每种长度的木板均可购买任意多块。为了避免浪费，所有木板的总长度必须恰好等于栅栏的长度。

给定栅栏的总长度 $L$ 以及可以购买的 $N$ 种木板长度，请求出恰好拼成长度 $L$ 所需的最少木板数量。如果无法恰好拼出长度 $L$，则报告无解。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例包含两行：

• 第一行包含两个以空格分隔的整数 $L$ 和 $N$，分别表示栅栏的总长度和可购买的木板长度种数；
• 第二行包含 $N$ 个以空格分隔的整数 $B_1,B_2,\ldots,B_N$，表示各种木板的长度。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: M，其中 $x$ 为从 $1$ 开始的测试用例编号。

如果可以购买一块或多块木板，使其总长度恰好等于 $L$，则 $M$ 为所需木板的最少数量；否则，$M$ 为字符串 IMPOSSIBLE。

样例输入

2
10000000001 3
23 51 100
10000000001 3
100 52 22

样例输出

Case #1: 100000004
Case #2: IMPOSSIBLE

样例解释

在第一个测试用例中，最优方案是使用 $2$ 块长度为 $23$ 的木板、$5$ 块长度为 $51$ 的木板，以及 $10^8-3$ 块长度为 $100$ 的木板，共使用 $10^8+4$ 块木板。

虽然仅使用 $10^8+1$ 块长度为 $100$ 的木板可以使总长度超过 $L$，但题目要求总长度必须恰好等于 $L$，因此这种方案不符合要求。

在第二个测试用例中，所有可购买的木板长度均为偶数，因此只能拼出偶数长度，无法拼出给定的奇数长度。

数据范围

• $1\le T\le 50$；
• $10^{10}\le L\le 10^{18}$；
• $1\le N\le 100$；
• 小数据中，$1\le B_i\le 100$；
• 大数据中，$1\le B_i\le 10^5$。

来源与许可

本题为 Google Code Jam 2010 试题「Fence」，题面与测试数据整理自 BZOJ。

样例 1

输入

2
10000000001 3
23 51 100
10000000001 3
100 52 22

输出

Case #1: 100000004
Case #2: IMPOSSIBLE