删除与拼接AI (CI翻译)
You are given an array $a$ of $n$ integers. Your initial score is $0$.
你有一个包含 $n$ 个整数的数组 $a$。初始分数为 $0$。AI (CI翻译)
You can perform the following two types of operations any number of times until the array becomes empty:
你可以执行以下两种操作任意次，直到数组变为空：AI (CI翻译)
- 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.)
- 选择一个元素。将其值加到你的分数中，并将该元素从数组中删除。
- 选择两个相邻元素。将它们的最大值加到你的分数中，并将这两个元素从数组中删除。（执行此操作时，数组中至少需要有
$2$个元素。）
After each operation, the remaining elements are concatenated without changing their relative order.
每次操作后，剩余元素会在不改变相对顺序的情况下拼接起来。AI (CI翻译)
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.
此外，给定一个整数 $c$，表示执行一次操作的代价。每次执行操作时（无论操作类型），都会从分数中减去 $c$。AI (CI翻译)
Compute the maximum possible final score you can achieve.
请计算你能够得到的最终分数的最大值。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个测试包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。AI (CI翻译)
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.
每个测试用例的第一行包含两个整数 $n$ 和 $c$（$1 \le n \le 2 \cdot 10^5$，$0 \le c \le 10^9$），分别表示数组 $a$ 的长度以及执行一次操作的代价。AI (CI翻译)
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$.
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9 \le a_i \le 10^9$），表示数组中的元素。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, output an integer representing the maximum possible score you can achieve.
对于每个测试用例，输出一个整数，表示你能够得到的最终分数的最大值。AI (CI翻译)
Note
说明
AI (CI翻译)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$.
在第一个测试用例中，唯一可能的选择是执行一次第一种操作。此时分数为 $a_1-c=-1-0=-1$。AI (CI翻译)
In the second test case, one optimal sequence of operations is:
在第二个测试用例中，一种最优操作序列如下：AI (CI翻译)
- 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.
- 选择
$3$。分数变为$0+3-0=3$，数组变为$[1,1]$。 - 选择第一个
$1$。分数变为$3+1-0=4$，数组变为$[1]$。 - 选择
$1$。分数变为$4+1-0=5$，数组变为空数组。
In the third test case, one optimal sequence of operations is:
在第三个测试用例中，一种最优操作序列如下：AI (CI翻译)
- 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.
- 选择
$3$和第二个$1$。分数变为$0+\max(3,1)-2=1$，数组变为$[1]$。 - 选择
$1$。分数变为$1+1-2=0$，数组变为空数组。
样例
5
1 0
-1
3 0
1 3 1
3 2
1 3 1
6 6
3 1 4 1 5 9
4 1000000000
-1000000000 -1000000000 -1000000000 -1000000000
-1
5
0
0
-4000000000
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。