Sequence Cost ~ Multiplex Coder

MoEngage has given you an array

$A$ of $N$ integers and a positive integer $C$ .

You can apply the following operation on the array any number of times. In one operation:

Choose a strictly increasing array of length such that:
- $B_{1} = 1, B_{M} = N,$ and $1 < B_{i} < N$ for all $(1 < i < M)$ ;
- $A_{B_{i}} > 0$ for all $(1 \leq i \leq M)$ .
Subtract $1$ from $A_{B_{i}}$ for all $(1 \leq i \leq M)$ .
The cost of this operation is $\sum_{i = 1}^{(M - 1)} (B_{i + 1} - B_{i})^{2}$ .

Note that, $M$ can be different for different operations.

Let $K$ be the total cost after performing $X$ number of operations on the array. Your goal is to maximize the value of $(C \cdot X - K)$ .

First line contains a single integer $T$ , denoting the number of test cases.
For each of the $T$ test cases, the first line contains two integers $N$ and $C$ .
The next line contains $N$ space-separated integers denoting $A_{1}, A_{2}, \dots, A_{N}$ .

For each test case, output a single integer - the maximum value of $(C \cdot X - K)$ .

3
3 3
3 1 5
7 5
5 5 5 4 1 2 1
2 10
3 3

1
0
27

Test case $1$ : Given $N = 3$ , $A = [3, 1, 5]$ , $C = 3$ .
It is optimal to apply only $1$ operation with $B = [1, 2, 3]$ . The cost for the operation would be $(2 - 1)^{2} + (3 - 2)^{2} = 2$ . The value of $X = 1$ and the total cost $K = 2$ . Thus, $(C \cdot X - K) = (3 \cdot 1 - 2) = 1$ .
After the operation, the array becomes $A = [2, 0, 4]$ .
Test case $2$ : Given $N = 7$ , $A = [5, 5, 5, 4, 1, 2, 1]$ , $C = 5$ .
It can be proven that it is never optimal to apply any operation. Hence, the answer will be $(5 \cdot 0 - 0) = 0$ .
Test case $3$ : Given $N = 2$ , $A = [3, 3]$ , $C = 10$ .
It is optimal to apply $3$ operations on the array. In each operation, it is optimal to take $B = [1, 2]$ . The cost for each operation would be $(2 - 1)^{2} = 1$ . Thus, $X = 3$ and total cost $K = 1 + 1 + 1 = 3$ . Thus, $(C \cdot X - K) = (10 \cdot 3 - 3) = 27$ .
After all the operations, the array becomes $A = [0, 0]$ .