← 返回题目列表

Codeforces · 1592/A

A. 玩家 Hemose

中文机器翻译题面 查看原题

有一天,Ahmed_Hossam 去 Hemose 说“我们来解决一场体操比赛吧!”。 Hemose 不想这样做,因为他正在玩《Valorant》,所以他提出了一个问题并告诉 Ahmed 以分散他的注意力。遗憾的是,艾哈迈德无法解决这个问题...你能帮助他吗?

《Valorant》中有一名特工,他拥有 $$$n$$$ 武器。第 $$$i$$$ 武器的伤害值为 $$$a_i$$$,特工将面对生命值为 $$$H$$$ 的敌人。

特工将执行一个或多个动作,直到敌人死亡。

在一个动作中,他将选择一件武器并根据其伤害值减少敌人的生命值。当敌人的生命值低于或等于$$$0$$$时,敌人就会死亡。然而,并非一切都那么容易:特工不能连续 $$$2$$$ 次选择相同的武器。

特工需要使用武器杀死敌人的最少次数是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ $$$(1 \leq t \leq 10^5)$$$。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$H$$$ $$$(2 \leq n \leq 10^3, 1 \leq H \leq 10^9)$$$ — 敌人的可用武器数量和初始生命值。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — 武器的伤害值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 特工必须使用武器杀死敌人的最小次数。

示例

输入 #1

3
2 4
3 7
2 6
4 2
3 11
2 1 7

输出 #1

1
2
3

注意

在第一个测试用例中,特工可以使用第二武器,使敌人的生命值等于$$$4-7=-3$$$。 $$$-3 \le 0$$$,所以敌人已经死了,使用武器$$$1$$$时间就足够了。

在第二个测试用例中,特工可以先使用第一个武器,然后再使用第二个。此后,敌人的生命值将下降到$$$6-4-2 = 0$$$,这意味着他将在使用武器$$$2$$$次后被杀死。

在第三个测试用例中,特工可以按顺序(第三、第一、第三)使用武器,在使用武器 $$$3$$$ 次后,将敌人的生命值降低到 $$$11 - 7 - 2 - 7 = -5$$$。请注意,我们不能两次使用第三种武器杀死敌人,因为即使$$$11-7-7<0$$$,也不允许连续使用同一武器两次。