减半或减法

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的正整数数组 $a$、正整数 $b$，以及两种操作：

1. 选择一个元素 $a_i$，将它变为 $\lceil a_i/2\rceil$；
2. 选择一个元素 $a_i$，将它变为 $\max(a_i-b,0)$。

第一种操作至多使用 $k_1$ 次，第二种操作至多使用 $k_2$ 次。对每个元素，每种操作都至多使用一次；同一个元素可以各使用一次，且可以自行选择操作顺序。

求操作后数组元素和的最小值。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例第一行包含 $n,b,k_1,k_2$，第二行包含 $n$ 个整数 $a_i$。

输出格式

对每个测试用例输出一行一个整数，表示最小元素和。

样例输入

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

数据范围

$1\le t\le5000$，$1\le n\le5000$，$1\le b,a_i\le10^9$，$0\le k_1,k_2\le n$，且单文件内 $\sum n\le5000$。

各子任务数据彼此独立计分。