P16752 [GKS 2020 #B] Bus Routes

Bucket 计划乘坐巴士进行长途乡村旅行。她的旅行包括 $N$ 条巴士路线，按她必须乘坐的顺序编号为 $1$ 到 $N$。巴士本身速度很快，但运行频率不高。第 $i$ 条巴士路线每 $X_i$ 天才运行一次。 更具体地说，她只能在第 $X_i$、$2X_i$、$3X_i$ 等天数乘坐第 $i$ 条巴士。由于巴士速度很快，她可以在同一天乘坐多辆巴士。 Bucket 必须在第 $D$ 天之前（含第 $D$ 天）完成她的旅程，但她希望尽可能晚地开始旅程。她能够乘坐第一辆巴士的最晚天数是多少，同时仍然能在第 $D$ 天之前完成旅程？ 保证 Bucket 有可能在第 $D$ 天之前完成她的旅程。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $D$。随后一行包含 $N$ 个整数，其中第 $i$ 个整数是 $X_i$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是她能乘坐第一辆巴士的最晚天数，同时仍能在第 $D$ 天之前完成旅程。

在样例 #1 中，有 $N = 3$ 条巴士路线，Bucket 必须在第 $D = 10$ 天之前到达。她可以： - 在第 $6$ 天乘坐第 $1$ 条巴士（$X_1 = 3$）， - 在第 $7$ 天乘坐第 $2$ 条巴士（$X_2 = 7$）， - 在第 $8$ 天乘坐第 $3$ 条巴士（$X_3 = 2$）。 在样例 #2 中，有 $N = 4$ 条巴士路线，Bucket 必须在第 $D = 100$ 天之前到达。她可以： - 在第 $99$ 天乘坐第 $1$ 条巴士（$X_1 = 11$）， - 在第 $100$ 天乘坐第 $2$ 条巴士（$X_2 = 10$）， - 在第 $100$ 天乘坐第 $3$ 条巴士（$X_3 = 5$）， - 在第 $100$ 天乘坐第 $4$ 条巴士（$X_4 = 50$）。 在样例 #3 中，有 $N = 1$ 条巴士路线，Bucket 必须在第 $D = 1$ 天之前到达。她可以： - 在第 $1$ 天乘坐第 $1$ 条巴士（$X_1 = 1$）。 ### 限制条件 $1 \le T \le 100$。 $1 \le X_i \le D$。 $1 \le N \le 1000$。 保证 Bucket 有可能在第 $D$ 天之前完成她的旅程。 **测试集 1** $1 \le D \le 100$。 **测试集 2** $1 \le D \le 10^{12}$。 翻译由 DeepSeek V4 Pro 完成