Maximum Subarray

2000ms

524288K

Description:

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')$$$.

Input:

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$$$.

Output:

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

Sample Input:

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

Sample Output:

Informação

Provedor Codeforces

Código CF1796D