Alice 和 Bob 正在玩游戏。他们有一个数组 $$$a_1, a_2,\ldots,a_n$$$。游戏分为两个步骤:
- 首先,Alice 将从数组中删除最多 $$$k$$$ 个元素。
- 其次,Bob 最多将数组的 $$$x$$$ 元素乘以 $$$-1$$$。
Alice 想要最大化数组元素的总和,而 Bob 想要最小化它。如果双方都发挥最佳,则在比赛结束后求数组元素之和。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — 数组中的元素数量、Alice 可以删除的数组元素数量限制以及限制Bob 可以将 $$$-1$$$ 乘以的数组元素的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — 数组的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳,则游戏结束后数组元素的总和。
示例
输入 #1
8 1 1 1 1 4 1 1 3 1 2 4 6 6 3 1 4 3 2 5 6 6 6 1 3 7 3 3 32 15 8 5 3 5 5 3 3 3 2 9 9 10 6 4 1 8 2 9 3 3 4 5 3 200 2 2 1 4 3 2 1 2 1 3
输出 #1
0 2 0 3 -5 -9 0 -1
注意
在第一个测试用例中,Alice 最好删除数组的唯一元素。那么,游戏结束后,数组元素的总和为$$$0$$$。
在第二个测试用例中,Alice 最好不要删除任何元素。然后 Bob 将 $$$4$$$ 乘以 $$$-1$$$。所以最终数组元素之和为$$$3+1+2-4=2$$$。
在第五个测试用例中,Alice 最好删除 $$$9, 9$$$。然后 Bob 将 $$$5, 5, 3$$$ 乘以 $$$-1$$$。所以数组元素的最终总和是$$$-5-5-3+3+3+2=-5$$$。