CF2245B Delete and Concatenate

You are given an array $ a $ of $ n $ integers. Your initial score is $ 0 $ . You can perform the following two types of operations any number of times until the array becomes empty: - Choose a single element. Add its value to your score, and remove it from the array. - Choose two adjacent elements. Add the maximum of their values to your score, and remove both elements from the array. (This operation requires the array to have at least $ 2 $ elements.) After each operation, the remaining elements are concatenated without changing their relative order. You are also given an integer $ c $ , which represents the cost of performing one operation. Every time you perform an operation (regardless of the type), $ c $ is subtracted from your score. Compute the maximum possible final score you can achieve.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ c $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 0 \le c \le 10^9 $ ), representing the length of $ a $ and the cost of performing one operation, respectively. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ -10^9 \le a_i \le 10^9 $ ), representing the elements of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output an integer representing the maximum possible score you can achieve.

In the first test case, your only possible choice is to perform the first operation once. Your score is $ a_1-c=-1-0=-1 $ . In the second test case, one optimal sequence of operations is: - Choose $ 3 $ . Your score becomes $ 0+3-0=3 $ , and the array becomes $ [1,1] $ . - Choose the first $ 1 $ . Your score becomes $ 3+1-0=4 $ , and the array becomes $ [1] $ . - Choose $ 1 $ . Your score becomes $ 4+1-0=5 $ , and the array becomes empty. In the third test case, one optimal sequence of operations is: - Choose $ 3 $ and the second $ 1 $ . Your score becomes $ 0+\max(3,1)-2=1 $ , and the array becomes $ [1] $ . - Choose $ 1 $ . Your score becomes $ 1+1-2=0 $ , and the array becomes empty.