题目内容

在一项能源优化任务中，有 $n$ 个能量核心，第 $i$ 个核心的初始能量值为 $v_i$。现可执行两类衰减操作：

• 折半操作：选择一个核心，将其能量值替换为 $\left\lfloor \frac{v_i}{2} \right\rfloor$；
• 削减操作：选择一个核心，将其能量值减少一个固定值 $d$，允许变为负数。

每个核心至多被施加一次折半操作，也至多被施加一次削减操作。允许对一个核心同时施加两种操作，顺序任意。 工程师总共可以执行折半操作至多 $p$ 次，削减操作至多 $q$ 次。 试求合理运用这些操作后，所有核心能量之和的最小可能值。

数据范围：测试数据组数 $T$ 不超过 2*10^5；每组数据中 $n$ 不超过 2*10^5，$p$ 和 $q$ 的取值范围为 $0$ 到 $n$，常数 $d$ 不超过 10^9，初始能量 $v_i$ 均为不超过 10^9 的正整数。所有测试数据的 $n$ 总和不超过 4*10^5。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来每组数据格式如下：第一行包含四个整数 $n, p, q, d$，含义见题面；第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$，表示各核心的初始能量值。

输出描述

对于每组测试数据，输出一行一个整数，表示最小的总能量值。

样例1

输入

2
4 2 1 10
12 5 8 3
3 0 3 5
2 4 6

输出

8
-3

说明

第一组数据： $n=4, p=2, q=1, d=10$，初始能量为 $[12,5,8,3]$，总和 28。 一次折半操作将能量变为 $\lfloor v/2 \rfloor$，减少量为 $\lceil v/2 \rceil$，即 $(v+1)//2$。各核心的折半收益依次为：12 收益 6，5 收益 3，8 收益 4，3 收益 2。 选择收益最大的 2 个核心（12 和 8）施加折半，共减少 10；削减操作执行 1 次，固定减少 10。 最终总和 $28 - 10 - 10 = 8$。

第二组数据： $n=3, p=0, q=3, d=5$，初始能量 $[2,4,6]$，总和 12。 折半操作次数为 0，无法使用。削减操作对 3 个核心各执行 1 次，每次减少 5，共计减少 15。 最终总和 $12 - 15 = -3$。

样例2

输入

1
3 2 0 100
7 9 2

输出

9

说明

$n=3, p=2, q=0, d=100$，初始能量 $[7,9,2]$，总和 18。 削减操作次数为 0，无法使用。 折半收益：$7$ 收益 $\lceil 7/2 \rceil = 4$，$9$ 收益 $\lceil 9/2 \rceil = 5$，$2$ 收益 $\lceil 2/2 \rceil = 1$。 选取收益最大的 2 个核心（9 和 7）执行折半，共减少 9。 最终总和 $18 - 9 = 9$。

样例3

输入

1
1 1 1 10
5

输出

-8

说明

单个核心 $n=1, p=1, q=1, d=10$，初始能量 5。 折半收益为 $\lceil 5/2 \rceil = 3$；削减操作固定减少 10。 两种操作均施加于该核心，总减少 13。 最终能量 $5 - 13 = -8$。