CF1796D.Maximum Subarray

You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ integers. You are also given two integers $k$ and $x$.

You have to perform the following operation exactly once: add $x$ to the elements on exactly $k$ distinct positions, and subtract $x$ from all the others.

For example, if $a = [2, -1, 2, 3]$, $k = 1$, $x = 2$, and we have picked the first element, then after the operation the array $a = [4, -3, 0, 1]$.

Let $f(a)$ be the maximum possible sum of a subarray of $a$. The subarray of $a$ is a contiguous part of the array $a$, i. e. the array $a_i, a_{i + 1}, \dots, a_j$ for some $1 \le i \le j \le n$. An empty subarray should also be considered, it has sum $0$.

Let the array $a'$ be the array $a$ after applying the aforementioned operation. Apply the operation in such a way that $f(a')$ is the maximum possible, and print the maximum possible value of $f(a')$.

给你一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$，以及两个整数 $k$ 和 $x$。

你必须恰好执行一次如下操作：在恰好 $k$ 个互不相同的位置上的元素加上 $x$，而对其余所有位置上的元素减去 $x$。

例如，若 $a = [2, -1, 2, 3]$，$k = 1$，$x = 2$，且我们选择了第一个元素，则操作后数组变为 $a = [4, -3, 0, 1]$。

令 $f(a)$ 表示数组 $a$ 的子数组最大和。这里子数组指 $a$ 的一个连续部分，即形如 $a_i, a_{i + 1}, \dots, a_j$ 的数组（其中 $1 \le i \le j \le n$）。空子数组也需考虑，其和为 $0$。

令 $a'$ 表示对 $a$ 执行上述操作后得到的数组。请以使得 $f(a')$ 尽可能大的方式执行该操作，并输出 $f(a')$ 的最大可能值。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $k$ and $x$ ($1 \le n \le 2 \cdot 10^5$; $0 \le k \le \min(20, n)$; $-10^9 \le x \le 10^9$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$).

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $x$（$1 \le n \le 2 \cdot 10^5$；$0 \le k \le \min(20, n)$；$-10^9 \le x \le 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$）。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the maximum possible value of $f(a')$.

对于每个测试用例，输出一个整数——$f(a')$ 的最大可能值。