牛马计划

题目描述

你因为经济原因，决定利用业余时间做一些兼职工作来赚取额外的收入。

你有 $n$ 种兼职工作，第 $i$ 种工作每做一次可以赚到 $a_i$ 元。

你每天 最多只能做一份工作。 不过，为了保证自己的身体健康并且不至于太过劳累，你决定引入一个限制参数 $k$ ，规定 同一种工作在做完之后的接下来的 $k$ 天内都不能再做。

• 例如，当 $k = 2$ 时： 如果你在第 1 天做了工作 A，那么第 2 天和第 3 天都不能再做 A，第 4 天才可以再次选择 A。

现在你给自己定下了一个目标：在 $d$ 天内至少赚到 $c$ 元钱。

请你计算：最大的 $k$ 是多少，仍然能保证你完成这个赚钱目标？

输入格式

输入包含多组测试数据。

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

对于每组数据：

• 第一行三个整数 $n, c, d$（$2 \le n \le 2 \times 10^5$，$1 \le c \le 10^{14}$，$1 \le d \le 2 \times 10^5$），分别表示可选工作的种类数、目标赚取金额和可工作的天数。

• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每种工作一次能赚到的钱数。

保证所有测试数据中：$n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出以下三种情况之一：

• Impossible: 无论怎么安排工作，都无法在 $d$ 天内赚到 $c$ 元。
• Infinity: 即使 $k$ 非常大（限制再严格），依然能完成目标。
• 一个非负整数: 表示满足条件的 最大 $k$。

**注意：输出区分大小写。**你需要严格按照题目要求输出字符串。

样例 1

6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1

2
Infinity
Impossible
1
12
0

提示

对于样例一组： 你有两种兼职，收入分别是 1 元和 2 元，需要在 4 天内赚 5 元。

当 $k = 2$ 时，一种可行方案是：

总收入 = 5，目标达成。

对于样例二组： 你有两种兼职，收入分别是 100 元和 10 元，需要在 10 天内赚 20 元。 无论 $k$ 多大，你可以在第一天做赚 100 元的工作，目标达成。

对于样例三组： 你有三种兼职，收入分别是 7 元、2 元和 6 元，需要在 3 天内赚 100 元。 即使 $k$ = 0，那么无论如何安排工作，你最多只能赚 21 元，目标无法达成。