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 python3.

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:
```python
<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.