最大子数组

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定长度为 $n$ 的整数数组 $a$，以及整数 $k,x$。你必须恰好选择 $k$ 个不同位置：给这些位置的元素加上 $x$，并给其余位置的元素减去 $x$。

一次操作后得到数组 $a'$。定义 $f(a')$ 为 $a'$ 的最大子数组和；允许选择空子数组，其和为 $0$。你需要选择这 $k$ 个位置，使 $f(a')$ 尽可能大，并输出最大值。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试：

• 第一行三个整数 $n,k,x$；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试输出一行一个整数，表示能得到的最大子数组和。

样例输入 1

4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8

样例输出 1

5
7
0
44

数据范围

对所有数据，$1\le t\le10^4$，$1\le n\le2\times10^5$，$0\le k\le\min(20,n)$，$-10^9\le x,a_i\le10^9$，所有测试组的 $n$ 之和不超过 $2\times10^5$。