← 返回题目列表

Codeforces · 1703/G

G. 好钥匙,坏钥匙

中文机器翻译题面 查看原题

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

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

- 一把好钥匙,使用时需要花费 $$$k$$$ 硬币;
- 一把坏钥匙,不会花费任何金币,但会将每个未打开的箱子中的所有硬币减半,包括即将打开的箱子。对于每个减半的箱子,减半操作将向下舍入到最接近的整数。换句话说,使用坏钥匙打开箱子 $$$i$$$ 将执行 $$$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$$$;
- 任何键(无论好键还是坏键)在使用后都会损坏,也就是说,它是一次性使用。

您总共需要使用 $$$n$$$ 钥匙,每个箱子一把。最初,您没有硬币,也没有钥匙。如果你想使用一把好的钥匙,那么你需要购买它。

在此过程中,您可以负债;例如,如果你有$$$1$$$币,那么你可以购买一把价值$$$k=3$$$币的好钥匙,你的余额将变成$$$-2$$$币。

按从 $$$1$$$ 到 $$$n$$$ 的顺序打开所有 $$$n$$$ 宝箱后可以拥有的最大金币数量。

输入

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

输出

对于每个测试用例,输出一个整数 - 按照从箱子 $$$1$$$ 到箱子 $$$n$$$ 的顺序打开箱子后可以获得的最大硬币数量。

请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。

示例

输入 #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

注意

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

- 用 $$$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$$$。