题目思路

对Bob来说，肯定是选择最大的m个数乘以-k，这样就可以让剩余数之和最小。

对于Alice来说，它可以选择去除0-d个元素。考虑去除x个元素，去除一个大的元素肯定比去除一个小的元素划算，因为大的那个乘以-k必然损失更大，所以Alice在去掉x个元素的情况下肯定是选择最大的x个元素去掉。

直接遍历去掉0-d个元素的所有情况，可以使用前缀和来维护Bob需要乘的值，时间复杂度$O(n)$

代码

题目描述

这里有几个正整数，$a_1,...,a_n$，Alice 会先去掉其中最多 $d$个数

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

Alice 想要剩余数之和尽可能大，Bob 想要剩余数之和尽可能小。

假设 Alice 和 Bob 都足够聪明，请问最后剩余数之和是多少。

输入描述

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

每组数据$2$行

• 第一行4个数, $n,m,k,d(2\le n\le10^5)$$(0\le m,d\le n)(1\le k \le 10^4)$
• 第二行$n$个数，$a_1,a_2,...,a_n(1\le a_i\le 10^9)$

保证 $\sum{n}$ 不超过$10^5$

输出描述

输出$T$个整数，表示每组数据的剩余数之和

样例

输入

1
3 1 1 1
4 3 2

输出

1

说明

Alice不会去掉任何数
Bob会把4变为-4，此时剩余数为[-4,3,2]，和为1