你有一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$。您还将获得一个正整数 $$$b$$$。
您可以按任意顺序执行以下操作(可能多次):
1. 选择一些 $$$1 \le i \le n$$$,并将 $$$a_i$$$ 替换为 $$$\lceil \frac{a_i}{2} \rceil$$$。这里,$$$\lceil x \rceil$$$表示不小于$$$x$$$的最小整数。
2. 选择一些 $$$1 \le i \le n$$$,并将 $$$a_i$$$ 替换为 $$$\max(a_i - b, 0)$$$。
但是,您还必须遵守以下规则:
- 您总共最多可以执行 $$$k_1$$$ 类型 1 的操作。
- 您总共最多可以执行 $$$k_2$$$ 类型 2 的操作。
- 对于所有$$$1 \le i \le n$$$,您最多可以对元素$$$a_i$$$执行类型1的$$$1$$$操作。
- 对于所有$$$1 \le i \le n$$$,您最多可以对元素$$$a_i$$$执行类型2的$$$1$$$操作。
数组的成本是其元素的总和。找出通过执行这些操作可以实现的最低成本 $$$a$$$。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$,即测试用例的数量 ($$$1 \le t \le 5000$$$)。
每个测试用例的第一行包含 $$$n$$$、$$$b$$$、$$$k_1$$$ 和 $$$k_2$$$ ($$$1 \le n \le 5000$$$、$$$1 \le b \le 10^9$$$、$$$0 \le k_1、k_2 \le n$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 描述数组 $$$a$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,打印通过执行操作可以实现的最低成本 $$$a$$$。
示例
输入 #1
7 3 2 1 1 9 3 5 2 1 2 0 1000000000 1 5 3 1 1 2 8 3 19 3 6 9 4 2 1 2 3 4 5 6 3 10 3 3 1 2 3 5 1 0 0 999999999 999999999 999999999 999999999 999999999 5 5 4 3 5 9 10 7 4
输出 #1
11 500000001 23 6 0 4999999995 6
注意
在第一个测试用例中,您可以执行以下操作:
- 对元素 $$$a_3$$$ 执行操作 2。它从 $$$5$$$ 变为 $$$3$$$。
- 对元素 $$$a_1$$$ 执行操作 1。它从 $$$9$$$ 变为 $$$5$$$。
经过这些操作,数组 $$$a = [5, 3, 3]$$$ 的成本为 $$$5 + 3 + 3 = 11$$$。我们可以证明这是可实现的最低成本。
在第二个测试用例中,请注意,我们不允许对 $$$a_1$$$ 多次执行操作 1。因此,最佳做法是对每个 $$$a_1$$$ 和 $$$a_2$$$ 应用一次操作 1。或者,我们可以仅对 $$$a_1$$$ 应用操作 1 一次,因为它对 $$$a_2$$$ 没有影响。
在第三个测试用例中,这是实现 $$$23$$$ 成本的一种方法:
- 将操作 1 应用于 $$$a_4$$$。它从 $$$19$$$ 变为 $$$10$$$。
- 将操作 2 应用于 $$$a_4$$$。它从 $$$10$$$ 变为 $$$7$$$。
经过这些操作,$$$a = [2, 8, 3, 7, 3]$$$。 $$$a$$$ 的成本为 $$$2 + 8 + 3 + 7 + 3 = 23$$$。我们可以证明这是可实现的最低成本。