CF1799F.Halve or Subtract

You have an array of positive integers $a_1, a_2, \ldots, a_n$, of length $n$. You are also given a positive integer $b$.

You are allowed to perform the following operations (possibly several) times in any order:

1. Choose some $1 \le i \le n$, and replace $a_i$ with $\lceil \frac{a_i}{2} \rceil$. Here, $\lceil x \rceil$ denotes the smallest integer not less than $x$.
2. Choose some $1 \le i \le n$, and replace $a_i$ with $\max(a_i - b, 0)$.

However, you must also follow these rules:

• You can perform at most $k_1$ operations of type 1 in total.
• You can perform at most $k_2$ operations of type 2 in total.
• For all $1 \le i \le n$, you can perform at most $1$ operation of type 1 on element $a_i$.
• For all $1 \le i \le n$, you can perform at most $1$ operation of type 2 on element $a_i$.

The cost of an array is the sum of its elements. Find the minimum cost of $a$ you can achieve by performing these operations.

你有一个长度为 $n$ 的正整数数组 $a_1, a_2, \ldots, a_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$ 执行 1 次 类型 2 的操作。

数组的代价定义为其所有元素之和。求通过执行上述操作所能达到的数组 $a$ 的最小代价。

Input consists of multiple test cases. The first line contains a single integer $t$, the number of test cases ($1 \le t \le 5000$).

The first line of each test case contains $n$, $b$, $k_1$, and $k_2$ ($1 \le n \le 5000$, $1 \le b \le 10^9$, $0 \le k_1, k_2 \le n$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ describing the array $a$ ($1 \le a_i \le 10^9$).

It is guaranteed the sum of $n$ over all test cases does not exceed $5000$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print the minimum cost of $a$ you can achieve by performing the operations.

对于每个测试用例，输出通过执行操作所能达到的 $a$ 的最小成本。

In the first test case, you can do the following:

• Perform operation 2 on element $a_3$. It changes from $5$ to $3$.
• Perform operation 1 on element $a_1$. It changes from $9$ to $5$.

After these operations, the array is $a = [5, 3, 3]$ has a cost $5 + 3 + 3 = 11$. We can show that this is the minimum achievable cost.

In the second test case, note that we are not allowed to perform operation 1 more than once on $a_1$. So it is optimal to apply operation 1 once to each $a_1$ and $a_2$. Alternatively we could apply operation 1 only once to $a_1$, since it has no effect on $a_2$.

In the third test case, here is one way to achieve a cost of $23$:

• Apply operation 1 to $a_4$. It changes from $19$ to $10$.
• Apply operation 2 to $a_4$. It changes from $10$ to $7$.

After these operations, $a = [2, 8, 3, 7, 3]$. The cost of $a$ is $2 + 8 + 3 + 7 + 3 = 23$. We can show that this is the minimum achievable cost.

在第一个测试用例中，你可以执行以下操作：

• 对元素 $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$ 的方法：

• 对 $a_4$ 执行操作 1。其值由 $19$ 变为 $10$。
• 对 $a_4$ 执行操作 2。其值由 $10$ 变为 $7$。

执行这些操作后，$a = [2, 8, 3, 7, 3]$。数组 $a$ 的代价为 $2 + 8 + 3 + 7 + 3 = 23$。我们可以证明这是可达到的最小代价。