题目描述

你有 $n$ 个箱子。第 $i$ 个箱子中有 $a_i$ 个硬币。你需要按照从箱子 $1$ 号到箱子 $n$ 号的顺序打开所有 $n$ 个箱子。

你可以用以下两种钥匙之一打开一个箱子：

• 好钥匙：使用一次消耗 $k$ 个硬币。
• 坏钥匙：使用时不消耗硬币，但会使所有未打开的箱子中的硬币数减半（包括正要打开的这个箱子）。硬币减半时向下取整。比如，用坏钥匙打开箱子 $i$ 号时，$a_i=a_i/2$，$a_{i+1}=a_{i+1}/2$，$......$，$a_n=a_n/2$。

所有钥匙用过一次就会断掉（别想着买一把好钥匙开完所有箱子了），好钥匙需要重复付费，坏钥匙效果会重复计算。

也就是说，你总共需要使用 $n$ 把钥匙，每个箱子用一把。开始时，你没有硬币和钥匙，如果想用好钥匙，你就得去买。值得注意的是，在这个过程中你可以赊账买钥匙；例如，如果你只有 $1$ 个硬币，你也可以购买价值 $k=3$ 个硬币的好钥匙，你的余额会变成 $-2$ 个硬币。

你需要求出开完所有箱子之后你能获得的最大硬币数量（显然大于等于 $0$ ）。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10 ^4$），表示测试数据的组数。

• 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^5$，$0 \leq k \leq 10^9$），分别表示箱子的个数和每把好钥匙的花费。
• 每组测试数据的第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$），表示每个箱子中硬币的数量。

所有测试数据中 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每组测试数据，输出对应的可获得的最大硬币数量。

提示（题面中给出）：开 $long$ $long$

5
4 5
10 10 3 1
1 2
1
3 12
10 10 29
12 51
5 74 89 45 18 69 67 67 11 96 23 59
2 57
85 60

11
0
13
60
58

提示

在第一个测试用例中，一种可能的策略如下：

1. 花费 5 枚金币购买一把好钥匙，打开宝箱 1，获得 10 枚金币。当前余额为 0 + 10 − 5 = 5 枚金币。
2. 花费 5 枚金币购买一把好钥匙，打开宝箱 2，获得 10 枚金币。当前余额为 5 + 10 − 5 = 10 枚金币。
3. 使用一把坏钥匙打开宝箱 3。由于使用了坏钥匙，宝箱 3 中的金币数变为 ⌊3 / 2⌋ = 1，宝箱 4 中的金币数变为 ⌊1 / 2⌋ = 0。当前余额为 10 + 1 = 11 枚金币。
4. 使用一把坏钥匙打开宝箱 4。由于使用了坏钥匙，宝箱 4 中的金币数变为 ⌊0 / 2⌋ = 0。当前余额为 11 + 0 = 11 枚金币。

最终，你拥有 11 枚金币，可以证明这是最大值。