题目描述

这里有n个正整数，a1, ... , an

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

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

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

输入描述

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

每组数据2行

第一行4个数

n, m, k, d (2 <= n <= 105), (0 <= m, d <= n), (1 <= k <= 104)

第二行n个数，a1, a2, ... , an (1 <= ai <= 109)

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

输出描述

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

输入示例

1
3 1 1 1
4 1 1

输出示例

0

提示信息

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

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

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