#P1735. 2024.3.24-PDD-第一题-剩余数最大和

2024.3.24-PDD-第一题-剩余数最大和

题目描述

这里有几个正整数，a1,...,ana_1,...,a_n，塔子哥 会先去掉其中最多 dd个数

小明 接下来会将剩余的数中最多mm个数乘以 −k-k

塔子哥 想要剩余数之和尽可能大，小明 想要剩余数之和尽可能小。

假设 塔子哥 和 小明 都足够聪明，请问最后剩余数之和是多少。

输入描述

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

每组数据2行

第一行4个数

$n,m,k,d(2\le n\le10^5)(0\le m,d\le n)(1\le k \le 10^4)$

第二行nn个数，a1,a2,...,an(1≤ai≤109)a_1,a_2,...,a_n(1\le a_i\le 10^9) 保证 ∑n\sum{n} 不超过10510^5

输出描述

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

样例

输入

1
3 1 1 1
4 3 2

输出

1

说明

塔子哥不会去掉任何数
小明会把4变为-4，此时剩余数为[-4,3,2]，和为1

知识点:*****

查看知识点以及同类型题目

Statistics