题目描述

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

打开每个箱子时，可以选择以下两种钥匙之一：

• 好钥匙：使用一次需要支付 $k$ 枚硬币；
• 坏钥匙：使用一次不需要支付硬币，但会将当前仍未打开的所有箱子（包括正在打开的这个箱子）中的硬币数都减半并向下取整。换句话说，若用坏钥匙打开第 $i$ 个箱子，则会同时令$$a_i=\left\lfloor\frac{a_i}{2}\right\rfloor,\ a_{i+1}=\left\lfloor\frac{a_{i+1}}{2}\right\rfloor,\ \ldots,\ a_n=\left\lfloor\frac{a_n}{2}\right\rfloor.$$

每把钥匙都是一次性的。开始时你没有硬币，也没有钥匙；若想使用好钥匙，就需要购买它。允许账户余额为负数。

打开箱子后，你会获得其中当时拥有的全部硬币。求打开所有箱子后，最多能拥有多少枚硬币。

输入格式

第一行一个整数 $t$（$1 \le t \le 10^4$），表示测试组数。

每组测试数据包含两行：

• 第一行两个整数 $n,k$（$1 \le n \le 10^5$，$0 \le k \le 10^9$），分别表示箱子数量和一把好钥匙的价格；
• 第二行 $n$ 个整数 $a_i$（$0 \le a_i \le 10^9$），表示各箱子的硬币数。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数，表示最后最多能拥有的硬币数。

答案可能超出 32 位整数范围，请使用至少 64 位整数类型。

样例

输入

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

样例说明

第一组可以先用两次好钥匙，分别打开前两个箱子；此时余额为 $10$。再用两次坏钥匙，第三、四个箱子中的硬币数依次变为 $1$ 和 $0$，最终余额为 $11$。