← 返回题目列表

Codeforces · 1759/E

E. 人形生物

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

有 $$$n$$$ 宇航员在某个空间站工作。编号为 $$$i$$$ ($$$1 \le i \le n$$$) 的宇航员拥有能力 $$$a_i$$$。

一个邪恶的人形生物已经前往这个空间站。这个人形生物的力量等于$$$h$$$。此外,人形生物还随身携带了两份绿色血清和一份蓝色血清。

在一秒钟内,人形机器人可以执行以下三个动作中的任何一个:

1.吸收一名宇航员,其力量严格小于人形力量;
2. 如果还有剩余的话,使用绿色血清;
3. 如果还有剩余,请使用蓝色血清。

当拥有$$$a_i$$$能力的宇航员被吸收时,该宇航员消失,人形生物的力量增加$$$\lfloor \frac{a_i}{2} \rfloor$$$,即$$$\frac{a_i}{2}$$$的整数部分。例如,如果一个人形生物吸收了一个力量为$$$4$$$的宇航员,它的力量会增加$$$2$$$,如果一个人形生物吸收了一个力量为$$$7$$$的宇航员,它的力量会增加$$$3$$$。

使用绿色血清后,这种血清消失,人形的力量加倍,因此增加了$$$2$$$倍。

使用蓝色血清后,这种血清消失,人形的力量增加了三倍,因此增加了$$$3$$$倍。

类人生物想知道如果他采取最佳行动,他最多能够吸收多少名宇航员。

输入

每个测试的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 宇航员数量和 $$$h$$$ ($$$1 \le h \le 10^6$$$) — 人形机器人的初始力量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^8$$$) — 宇航员的权力。

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

输出

对于每个测试用例,在单独的行中打印人形机器人可以吸收的最大宇航员数量。

示例

输入 #1

8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13

输出 #1

4
3
3
3
0
4
4
3

注意

对于第一种情况,您可以按照以下步骤操作:

1.使用绿色血清。 $$$h = 1 \cdot 2 = 2$$$
2.吸收宇航员$$$2$$$。 $$$h = 2 + \lfloor \frac{1}{2} \rfloor = 2$$$
3.使用绿色血清。 $$$h = 2 \cdot 2 = 4$$$
4.吸收太空人$$$1$$$。 $$$h = 4 + \lfloor \frac{2}{2} \rfloor = 5$$$
5.使用蓝色血清。 $$$h = 5 \cdot 3 = 15$$$
6.吸收太空人$$$3$$$。 $$$h = 15 + \lfloor \frac{8}{2} \rfloor = 19$$$
7.吸收宇航员$$$4$$$。 $$$h = 19 + \lfloor \frac{9}{2} \rfloor = 23$$$