CF1759E The Humanoid

题目描述

有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。 人型生物可以做以下三个动作: - 吸收一个能量值严格低于当前人型生物的宇航员。 - 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。 - 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。 其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。 请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量?

输入格式

第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。 对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。 保证 $\sum n\leq 2\cdot 10^5$。

输出格式

对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。

说明/提示

In the first case, you can proceed as follows: 1. use green serum. $ h = 1 \cdot 2 = 2 $ 2. absorb the cosmonaut $ 2 $ . $ h = 2 + \lfloor \frac{1}{2} \rfloor = 2 $ 3. use green serum. $ h = 2 \cdot 2 = 4 $ 4. absorb the spaceman $ 1 $ . $ h = 4 + \lfloor \frac{2}{2} \rfloor = 5 $ 5. use blue serum. $ h = 5 \cdot 3 = 15 $ 6. absorb the spaceman $ 3 $ . $ h = 15 + \lfloor \frac{8}{2} \rfloor = 19 $ 7. absorb the cosmonaut $ 4 $ . $ h = 19 + \lfloor \frac{9}{2} \rfloor = 23 $