去掉括号

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 和非负整数 $s$。

对于每个 $2\le i\le n-1$，选择一对非负整数 $x_i,y_i$，满足

$$x_i+y_i=a_i,\qquad (x_i-s)(y_i-s)\ge0.$$

定义

$$F=a_1x_2+y_2x_3+y_3x_4+\cdots+y_{n-2}x_{n-1}+y_{n-1}a_n.$$

请在所有合法选择中求出 $F$ 的最小值。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含两个整数 $n,s$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示 $F$ 的最小值。

样例输入 1

10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480

样例输出 1

0
18
32
11
14
0
16
0
40000000000
2700826806

数据范围

$1\le t\le10^4$，$3\le n\le2\cdot10^5$，$0\le s,a_i\le2\cdot10^5$，且所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。

子任务编号	分值	特殊限制
1	30	每个测试用例均满足 $n\le18$
2		每个测试用例均满足 $n\le2000$
3	40	无特殊限制