RSJ 有一个由 $$$n$$$ 整数 $$$a_1,a_2, \ldots, a_n$$$ 和一个整数 $$$s$$$ 组成的序列 $$$a$$$。对于每个 $$$a_2,a_3, \ldots, a_{n-1}$$$,他选择了一对非负整数 $$$x_i$$$ 和 $$$y_i$$$,使得 $$$x_i+y_i=a_i$$$ 和 $$$(x_i-s) \cdot (y_i-s) \geq 0$$$。
现在他对值 $$$$$$F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.$$$$$$ 感兴趣
请帮他找到通过最优选择$$$x_i$$$和$$$y_i$$$可以获得的最小可能值$$$F$$$。可以证明,总是至少有一种有效的方法来选择它们。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$s$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$0 \le s \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$)。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$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
注意
在第一个测试用例中,$$$2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$$$。
在第二个测试用例中,$$$5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$$$。