有一天,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$$$,也不允许连续使用同一武器两次。