CF1703G.Good Key, Bad Key

There are $n$ chests. The $i$-th chest contains $a_i$ coins. You need to open all $n$ chests in order from chest $1$ to chest $n$.

There are two types of keys you can use to open a chest:

• a good key, which costs $k$ coins to use;
• a bad key, which does not cost any coins, but will halve all the coins in each unopened chest, including the chest it is about to open. The halving operation will round down to the nearest integer for each chest halved. In other words using a bad key to open chest $i$ will do $a_i = \lfloor{\frac{a_i}{2}\rfloor}$, $a_{i+1} = \lfloor\frac{a_{i+1}}{2}\rfloor, \dots, a_n = \lfloor \frac{a_n}{2}\rfloor$;
• any key (both good and bad) breaks after a usage, that is, it is a one-time use.

You need to use in total $n$ keys, one for each chest. Initially, you have no coins and no keys. If you want to use a good key, then you need to buy it.

During the process, you are allowed to go into debt; for example, if you have $1$ coin, you are allowed to buy a good key worth $k=3$ coins, and your balance will become $-2$ coins.

Find the maximum number of coins you can have after opening all $n$ chests in order from chest $1$ to chest $n$.

共有 $n$ 个宝箱。第 $i$ 个宝箱中包含 $a_i$ 枚金币。你需要按顺序从第 $1$ 个宝箱到第 $n$ 个宝箱依次打开全部 $n$ 个宝箱。

打开一个宝箱时，你可以使用两种类型的钥匙：

• 优质钥匙：使用一次需花费 $k$ 枚金币；
• 劣质钥匙：使用不花费金币，但会使所有尚未打开的宝箱（包括即将打开的当前宝箱）中的金币数量减半（向下取整）。换言之，若用劣质钥匙打开第 $i$ 个宝箱，则会对所有 $j \in [i, n]$ 执行操作 $a_j = \left\lfloor \frac{a_j}{2} \right\rfloor$；
• 任意一种钥匙（优质或劣质）均仅能使用一次，即为一次性用品。

你总共需使用 $n$ 把钥匙，每把钥匙对应打开一个宝箱。初始时，你既没有金币，也没有任何钥匙。若想使用优质钥匙，则必须花钱购买。

在过程中允许透支；例如，若你当前仅有 $1$ 枚金币，仍可购买价值 $k = 3$ 的优质钥匙，此时你的余额将变为 $-2$ 枚金币。

求在按顺序从第 $1$ 个宝箱到第 $n$ 个宝箱全部打开后，你能拥有的最多金币数量。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$; $0 \leq k \leq 10^9$) — the number of chests and the cost of a good key respectively.

The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$) — the amount of coins in each chest.

The sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case output a single integer — the maximum number of coins you can obtain after opening the chests in order from chest $1$ to chest $n$.

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

对于每个测试用例，输出一个整数——即按从宝箱 $1$ 到宝箱 $n$ 的顺序打开所有宝箱后，你能获得的最多金币数量。

请注意，某些测试用例的答案无法用 32 位整数类型表示，因此在编程语言中你应至少使用 64 位整数类型（例如 C++ 中的 long long）。

In the first test case, one possible strategy is as follows:

• Buy a good key for $5$ coins, and open chest $1$, receiving $10$ coins. Your current balance is $0 + 10 - 5 = 5$ coins.
• Buy a good key for $5$ coins, and open chest $2$, receiving $10$ coins. Your current balance is $5 + 10 - 5 = 10$ coins.
• Use a bad key and open chest $3$. As a result of using a bad key, the number of coins in chest $3$ becomes $\left\lfloor \frac{3}{2} \right\rfloor = 1$, and the number of coins in chest $4$ becomes $\left\lfloor \frac{1}{2} \right\rfloor = 0$. Your current balance is $10 + 1 = 11$.
• Use a bad key and open chest $4$. As a result of using a bad key, the number of coins in chest $4$ becomes $\left\lfloor \frac{0}{2} \right\rfloor = 0$. Your current balance is $11 + 0 = 11$.

At the end of the process, you have $11$ coins, which can be proven to be maximal.

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

• 花费 $5$ 枚硬币购买一把好钥匙，打开宝箱 $1$，获得 $10$ 枚硬币。此时你的余额为 $0 + 10 - 5 = 5$ 枚硬币。
• 再花费 $5$ 枚硬币购买一把好钥匙，打开宝箱 $2$，获得 $10$ 枚硬币。此时你的余额为 $5 + 10 - 5 = 10$ 枚硬币。
• 使用一把坏钥匙打开宝箱 $3$。由于使用了坏钥匙，宝箱 $3$ 中的硬币数变为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，而宝箱 $4$ 中的硬币数变为 $\left\lfloor \frac{1}{2} \right\rfloor = 0$。此时你的余额为 $10 + 1 = 11$。
• 使用一把坏钥匙打开宝箱 $4$。由于使用了坏钥匙，宝箱 $4$ 中的硬币数变为 $\left\lfloor \frac{0}{2} \right\rfloor = 0$。此时你的余额为 $11 + 0 = 11$。

整个过程结束后，你共拥有 $11$ 枚硬币，可以证明这是最大值。