You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
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.

## Input Format
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$$$.

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

## Examples
```input
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
```
```output
11
500000001
23
6
0
4999999995
6
```

## Note
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.

Now solve the problem and return the code.