在回收中心,有$$$n$$$个垃圾袋,第$$$i$$$个垃圾袋的重量为$$$a_i$$$。每一秒,两个动作会连续发生:
- 首先,您必须选择一个垃圾袋并将其销毁。如果垃圾袋的重量严格大于$$$c$$$,则需要花费$$$1$$$硬币,否则需要花费$$$0$$$硬币。
- 然后,剩余每个垃圾袋的重量将乘以二。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq c \leq 10^9)$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 每个垃圾袋的重量。
输出
对于每个测试用例,您必须输出一个整数 - 销毁所有垃圾袋所需花费的最小硬币数量。
示例
输入复制
45 1010 4 15 1 83 421000000000 1000000000 100000000010 3029 25 2 12 15 42 14 6 16 910 10000001 1 1 1 1 1 1 1 1 864026633
输出复制
2 3 6 1
注意
在下面的解释中:
- 蓝色数字代表已免费销毁的垃圾袋,
- 红色数字代表已销毁 $$$1$$$ 硬币的垃圾袋,
- 黑色数字代表尚未销毁的垃圾袋。
在第一个测试用例中,一个解决方案是:
- $$$[10, 4, 15, 1, 8]$$$
- $$$[\color{blue}{10}, 8, 30, 2, 16]$$$,$$$10$$$ 被免费销毁,因为 $$$10 \leq 10$$$。
- $$$[\color{blue}{10}, \color{blue}{8}, 60, 4, 32]$$$, $$$8$$$ 被免费销毁,因为 $$$8 \leq 10$$$。
- $$$[\color{blue}{10}, \color{blue}{8}, 120, 8, \color{red}{32}]$$$, $$$32$$$ 被销毁为 $$$1$$$ 硬币,因为 $$$32 \gt 10$$$。
- $$$[\color{blue}{10}, \color{blue}{8}, 240, \color{blue}{8}, \color{red}{32}]$$$, $$$8$$$ 被免费销毁,因为 $$$8 \leq 10$$$。
- $$$[\color{blue}{10}, \color{blue}{8}, \color{red}{240}, \color{blue}{8}, \color{red}{32}]$$$, $$$240$$$ 被销毁为 $$$1$$$ 硬币,因为 $$$240 \gt 10$$$。
您总共支付了 $$$2$$$ 硬币,我们可以证明它是最优的。
在第二个测试用例中,一种解决方案是:
- $$$[1\,000\,000\,000, 1\,000\,000\,000, 1\,000\,000\,000]$$$
- $$$[\color{red}{1\,000\,000\,000}, 2\,000\,000\,000, 2\,000\,000\,000]$$$, $$$1\,000\,000\,000$$$ 被销毁为 $$$1$$$ 硬币,因为$$$1\,000\,000\,000 \gt 42$$$。
- $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, 4\,000\,000\,000]$$$, $$$2\,000\,000\,000$$$ 被销毁为 $$$1$$$ 硬币,因为$$$2\,000\,000\,000 \gt 42$$$。
- $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, \color{red}{4\,000\,000\,000}]$$$, $$$4\,000\,000\,000$$$ 被销毁$$$1$$$ 硬币,因为 $$$4\,000\,000\,000 \gt 42$$$。