#CF4057. 好钥匙坏钥匙

好钥匙坏钥匙

题目描述

nn 个箱子。第 ii 个箱子里有 aia_i 硬币。你需要打开所有 nn 个箱子,从箱子 11 到箱子 nn

有两种类型的钥匙可以用来打开箱子:

  • 一把好钥匙,要花 kk 个硬币;
  • 一把坏钥匙,不需要任何硬币,但会将每个未打开的箱子中的所有硬币减半,包括即将打开的箱子。减半操作将向下取整。换句话说,用一把坏钥匙打开箱子 ii,将会造成 $a_i=\lfloor \frac{x_i}2 \rfloor,a_{i+1}=\lfloor \frac{x_{i+1}}2 \rfloor,…,a_n=\lfloor \frac{x_n}2 \rfloor $。
  • 任何钥匙(好的和坏的)在使用后都会断开,也就是说,它是一次性使用。

你需要总共使用 nn 把钥匙,每个宝箱一个。最初,你没有硬币和钥匙。如果你想用一把好钥匙,那么你需要使用硬币购买。

并且在此过程中,你允许赊账;例如,如果你有 11 个硬币,你可以购买一把价值 k3k=3 个硬币的好钥匙,你的余额将变成 2-2 个硬币。

现在,求出按照从 11 号箱子到 nn 号箱子的顺序打开所有 nn 个箱子后,你能拥有的最大硬币数量。

输入格式

第一行包含单个整数 t(1t104)t(1≤t≤10^4) 代表测试用例数。

每个测试用例的第一行包含两个整数 nnk(1n1050k109)k(1≤n≤10^5,0≤k≤10^9),分别是箱子的数量和一把好钥匙的价格。

每个测试用例的第二行包含 nn 个整数 ai(0ai109)a_i(0≤a_i≤10^9) 代表每个箱子中的硬币数量。

所有测试用例的 nn 之和不超过 10510^5

输出格式

对于每个测试用例,输出一个整数,代表依次从 11nn 打开箱子后可以获得的最大硬币数量。

请注意,某些测试用例的答案可能超过 3232 位整数类型,因此您应该在编程语言中至少使用 6464 位整数类型。

测试样例

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

样例说明

在第一个测试案例中,一种可能的策略如下:

55 个硬币买一把好钥匙,打开箱子 11,收到 1010 个硬币。您当前的余额为 0+105=50+10−5=5 个硬币。

55 枚硬币买一把好钥匙,打开 22 号箱子,收到 1010 枚硬币。您当前的余额为 5+105=105+10−5=10 个硬币。

使用坏钥匙打开箱子 33。由于使用了坏钥匙,箱子 33 中的硬币数量变为 32=1\lfloor \frac32 \rfloor=1,箱子 44 中的硬币数变为 12=0\lfloor \frac12 \rfloor=0。您当前的余额为 10+1=1110+1=11

使用坏钥匙打开箱子 44。由于使用了坏钥匙,箱子 44 中的硬币数量变为 02=0\lfloor \frac02 \rfloor=0。您当前的余额为 11+0=1111+0=11

在这个过程的最后,你有 1111 个硬币,这可以被证明是最大的。