题目描述

在回收中心，有 $n$ 个垃圾袋，第 $i$ 个垃圾袋的重量为 $a_i$。每一秒钟，会依次发生以下两个操作：

• 首先，你必须选择一个垃圾袋并销毁它。如果该垃圾袋的重量严格大于 $c$，则需要花费 $1$ 个硬币，否则不需要花费硬币。
• 然后，剩余每个垃圾袋的重量都会变为原来的两倍。

你需要花费的最少硬币数是多少，才能销毁所有垃圾袋？

输入格式

每个测试点包含多组测试数据。第一行包含测试用例数 $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$），表示每个垃圾袋的重量。

输出格式

对于每组测试数据，输出一个整数，表示销毁所有垃圾袋所需的最少硬币数。

说明/提示

在下面的解释中：

• 蓝色数字表示被免费销毁的垃圾袋，
• 红色数字表示被花费 $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 > 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 > 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 > 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 > 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 > 42$。

由 ChatGPT 4.1 翻译

样例

4
5 10
10 4 15 1 8
3 42
1000000000 1000000000 1000000000
10 30
29 25 2 12 15 42 14 6 16 9
10 1000000
1 1 1 1 1 1 1 1 1 864026633

2
3
6
1