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:
However, you must also follow these rules:
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 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$$$.
For each test case, print the minimum cost of $$$a$$$ you can achieve by performing the operations.
73 2 1 19 3 52 1 2 01000000000 15 3 1 12 8 3 19 36 9 4 21 2 3 4 5 63 10 3 31 2 35 1 0 0999999999 999999999 999999999 999999999 9999999995 5 4 35 9 10 7 4
11 500000001 23 6 0 4999999995 6
In the first test case, you can do the following:
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$$$:
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.
Name |
---|