题目描述

有 $n$ 个任务。如果你完成第 $i$ 个任务，你将获得 $a_i$ 个金币。你每天最多只能完成一个任务。然而，一旦你完成了某个任务，在接下来的 $k$ 天内你不能再次完成同一个任务。（例如，如果 $k=2$，你在第 $1$ 天完成了任务 $1$，那么在第 $2$ 天和第 $3$ 天你都不能再次完成任务 $1$，但可以在第 $4$ 天再次完成。）

现在给定两个整数 $c$ 和 $d$。请你求出最大的 $k$，使得你在 $d$ 天内至少可以获得 $c$ 个金币。如果不存在这样的 $k$，输出 Impossible。如果 $k$ 可以任意大，输出 Infinity。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试数据的组数。接下来是每组测试数据的描述。

每组测试数据的第一行包含三个整数 $n, c, d$（$2 \leq n \leq 2 \cdot 10^5$；$1 \leq c \leq 10^{16}$；$1 \leq d \leq 2 \cdot 10^5$），分别表示任务数量、所需金币数量和天数。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示每个任务的奖励金币数。

所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试数据中 $d$ 的总和不超过 $2 \cdot 10^5$。

输出格式

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

• 如果不存在这样的 $k$，输出 Impossible。
• 如果 $k$ 可以任意大，输出 Infinity。
• 否则，输出一个整数，表示最大的 $k$，使得你在 $d$ 天内至少可以获得 $c$ 个金币。

请注意，判题器区分大小写，你需要严格按照题目要求输出字符串。

样例

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

样例说明

在第一个测试用例中，一种在 $4$ 天内用 $k=2$ 获得 $5$ 个金币的方法如下：

• 第 1 天：完成任务 2，获得 $2$ 个金币。
• 第 2 天：完成任务 1，获得 $1$ 个金币。
• 第 3 天：不做任何任务。
• 第 4 天：完成任务 2，获得 $2$ 个金币。

总共获得 $2+1+2=5$ 个金币。

在第二个测试用例中，我们可以在第一天通过完成第一个任务获得 $100$ 个金币，因此 $k$ 可以任意大，因为我们不需要再做其他任务。

在第三个测试用例中，无论怎么做，都无法在 $3$ 天内获得 $100$ 个金币。

由 ChatGPT 4.1 翻译

来源

Codeforces 1760F，英文题名 Quests。