Halve or Subtract

# Halve or Subtract ## 题目描述 给定一个长度为 $n$ 的数列 $ a_1, a_2, \ldots, a_n $ ，一个正整数 $b$ 和两种操作： 1. 选一个 $i$ 满足 $ 1 \le i \le n $ ，把 $ a_i $ 变为 $ \lceil \frac{a_i}{2} \rceil $ 。 2. 选一个 $i$ 满足 $ 1 \le i \le n $ ，把 $ a_i $ 变为 $ \max(a_i - b, 0) $ 。 同时给定两个非负整数 $0 \le k_1, k_2 \le n$， 要求至多进行 $k_1$ 次操作1， $k_2$ 次操作2，同时对于每个元素，每种操作至多进行一次。 求出进行若干次满足条件的操作后 $a_1 + a_2 + \ldots + a_n$ 的最小值。 ## 输入格式 多组数据， 第一行为数据组数 $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 $ ( $ 1 \le a_i \le 10^9 $ )。 保证所有数据的 $n$ 之和不超过 $5000$。 ## 输出格式 对于每组数据输出一行一个整数表示 $a_i$ 的和的最小值。

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

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

11
500000001
23
6
0
4999999995
6

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.