A. Recycling Center

问题描述

在回收中心，有 $n$ 个垃圾袋，第 $i$ 个袋子的重量为 $a_i$。在每一秒，会相继发生两个动作：

1. 首先，你必须选择一个垃圾袋并销毁它。如果垃圾袋的重量严格大于 $c$，将花费 1 个金币，否则花费 0 个金币。
2. 然后，每个剩余垃圾袋的重量将乘以二。

你需要花费最少数量的金币来处理掉所有的垃圾袋，这个最小值是多少？

输入

每个测试包含多个测试用例。第一行是测试用例的数量 $t$ $(1 \leq t \leq 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. 成本结构: 销毁一个垃圾袋，如果其重量 > $c$，则成本为 1 金币，否则免费。
2. 重量加倍: 每次销毁后，所有剩余袋子的重量都会加倍。
3. 最优策略: 我们想要最小化超过阈值 $c$ 的袋子数量。

提交链接