好钥匙与坏钥匙

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

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

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

• 好钥匙：支付 $k$ 枚硬币，再获得当前箱子中的全部硬币。支付后余额可以为负数。
• 坏钥匙：不支付硬币，但当前箱子和所有尚未打开的箱子中的硬币数都会除以 $2$ 并向下取整，随后获得当前箱子中的硬币。

每把钥匙只能使用一次，每个箱子都要使用一把新钥匙。求打开全部箱子后最多能拥有多少枚硬币。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含两个整数 $n,k$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示能获得的最大硬币数。

样例输入 1

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

样例输出 1

11
0
13
60
58

数据范围

$1\le t\le 10^4$，$1\le n\le 10^5$，$0\le k,a_i\le 10^9$，且所有测试用例的 $n$ 之和不超过 $10^5$。