有 $$$n$$$ 任务。如果您完成第 $$$i$$$ 个任务,您将获得 $$$a_i$$$ 硬币。您每天最多只能完成一项任务。但是,一旦完成任务,您就无法在 $$$k$$$ 天内再次执行相同的任务。 (例如,如果 $$$k=2$$$ 并且您在 $$$1$$$ 天执行了任务 $$$1$$$,那么您无法在 $$$2$$$ 或 $$$3$$$ 天执行任务,但您可以在 $$$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\cdot10^5$$$; $$$1 \leq c \leq 10^{16}$$$; $$$1 \leq d \leq 2\cdot10^5$$$) — 任务数量,数量您需要的硬币数量以及天数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 任务的奖励。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$,所有测试用例的 $$$d$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,输出以下内容之一。
- 如果不存在这样的 $$$k$$$ ,则输出 Impossible。
- 如果 $$$k$$$ 可以任意大,则输出 Infinity。
- 否则,输出一个整数 - $$$k$$$ 的最大值,这样您就可以在 $$$d$$$ 天内获得至少 $$$c$$$ 硬币。
示例
输入 #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
输出 #1
2 Infinity Impossible 1 12 0
注意
在第一个测试用例中,在 $$$4$$$ 天内赚取 $$$5$$$ 硬币($$$k=2$$$)的一种方法如下:
- 第 1 天:完成任务 2,并赚取 $$$2$$$ 硬币。
- 第 2 天:完成任务 1,并赚取 $$$1$$$ 硬币。
- 第三天:什么也不做。
- 第 4 天:完成任务 2,赚取 $$$2$$$ 硬币。
在第二个测试用例中,我们可以通过执行第一个任务在第一天赚取超过 $$$20$$$ 硬币来赚取 $$$100$$$ 硬币,因此 $$$k$$$ 的值可以是任意大,因为我们永远不需要做另一个任务。
在第三个测试用例中,无论我们做什么,我们都无法在 $$$3$$$ 天内赚取 $$$100$$$ 硬币。