这里有n个正整数，a₁, ... , a_n

Alice 会先去掉其中最多d个数

Bob 接下来会将剩余的数中最多m个数乘以 -k

Alice 想要剩余数之和尽可能大，Bob 想要剩余数之和尽可能小。假设 Alice 和 Bob 都足够聪明，请问最后剩余数之和是多少。

第一行一个正整数T，接下来有T组数据

每组数据2行

第一行4个数

n, m, k, d (2 <= n <= 10⁵), (0 <= m, d <= n), (1 <= k <= 10⁴)

第二行n个数，a₁, a₂, ... , a_n (1 <= a_i <= 10⁹)

保证所有数据的n之和不超过10⁵。

每组数据输出一行，每行一个数，表示剩余数之和。

1
3 1 1 1
4 1 1

0

Alice会去掉4，此时剩余数为[1, 1]

Bob会把一个1变为-1，此时剩余数为[-1, 1]，和为0。

时间限制：c/c++/go：1s；其他语言：3s。