题目内容

给定一个长度为 $n$ 的整数序列 ${a_1,a_2,…,a_n}$。

你可以对序列中的某些位置做操作。每个位置最多做一次操作 $1$，最多做一次操作 $2$（两种都做也可以，顺序任意），也可以完全不操作。 两种操作如下：

• 操作 $1$：选择一个位置 $i$，把 $a_i$ 变为 $\left\lfloor \dfrac{a_i}{2} \right\rfloor$（也就是除以 2 再向下取整）；
• 操作 $2$：选择一个位置 $i$，把 $a_i$ 变为 $a_i-k$（注意：允许变成负数）。

你最多可以执行操作 $1$ 共 $a$ 次，最多可以执行操作 $2$ 共 $b$ 次。请你选好如何操作，使最终序列所有元素之和尽可能小，输出这个最小可能的和。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1\le T\le 2\times 10^5$）代表数据组数，每组测试数据描述如下：

第一行输入四个整数 $n,a,b,k$（$1\le n\le 2\times 10^5;\ 0\le a\le n;\ 0\le b\le n;\ 1\le k\le 10^9$）。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$​（$1\le a_i\le 10^9$）。

除此之外，保证单个测试文件中所有测试数据的 $n$ 之和不超过 $4\times 10^5$。

输出描述

对于每组测试数据，新起一行输出一个整数，表示最小可能的最终元素和（这个数可能为负数）。

样例1

输入

3
3 1 1 3
5 1 7
1 1 1 5
9
1 0 1 10
3

输出

6
-1
-7

说明

对于第三组数据： $n=1,a=0,b=1,k=10$，序列为 $\{3\}$。 只能做一次操作 $2:3\rightarrow -7$，最终元素和为 $−7$。