hackercupai/hackercup huggingface dataset:
In preparation for his final exam, Ethan is doing his fourth programming
assignment: finding the subarray with the maximum sum in an array of integers.

Given an array of **N** integers **A1..N**, Ethan's task is to find the
maximum sum of any (possibly empty) contiguous subarray of **A**. Ethan has
implemented an algorithm to solve this problem, described by the following
pseudocode:

* 1\. Set **s** and **m** to both be equal to 0.
* 2\. Iterate _i_ upwards from 1 to **N**:
* 2a. If **Ai** ≥ 0, increment **s** by **Ai**, otherwise set **s** to be equal to 0.
* 2b. If **s** > **m**, set **m** to be equal to **s**.
* 3\. Output **m**.

Is there any hope for Ethan? With exasperation, you set out in vain to teach
another lesson.

The professor of the class has once again left you with some half-written test
cases. You're given an initial array **B1..M**, such that the absolute value
of each element is at most **K**. You'd like to insert **M** \- 1 more
integers into the array, one between each pair of adjacent elements in the
original array, to construct a new array **A1..N** where **N** = 2**M** \- 1.
Each of the inserted elements must likewise have an absolute value of at most
**K**. You'll then feed the new array **A** into Ethan's algorithm. Your goal
is to maximize the absolute difference between the final array's correct
maximum subarray sum and the output of Ethan's algorithm.

### Input

Input begins with an integer **T**, the number of test cases. For each test
case, there is first a line containing the space-separated integers **M** and
**K**. Then one more line follows containing the **M** space-separated
integers **B1** through **BM**.

### Output

For the _i_th test case, output a line containing "Case #_i_: " followed by
the maximum possible absolute difference between the correct maximum subarray
sum and the output of Ethan's algorithm.

### Constraints

1 ≤ **T** ≤ 60
1 ≤ **M** ≤ 50
1 ≤ **K** ≤ 50
-**K** ≤ **Ai** ≤ **K**

### Explanation of Sample

In the first case, **A** = [3], and both Ethan's answer and the correct answer
are equal to 3.

In the second case, **A** = [-3], and both Ethan's answer and the correct
answer are equal to 0.

In the third case, one value will be inserted into **B**, and you should
choose to insert -1 to yield **A** = [2, -1, 2]. This results in Ethan's
answer being 2 and the correct answer being 3, yielding an absolute answer
difference of 1.

In the fourth case, there are multiple choices of inserted elements which
result in an absolute answer difference of 3. For example, it's possible for
Ethan's answer equal to be made to equal 3 while the correct answer equals 6.