У RSJ есть последовательность $$$a$$$ из $$$n$$$ целых чисел $$$a_1,a_2, \ldots, a_n$$$ и целое число $$$s$$$. Для каждого $$$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.$$$$$$
Помогите ему найти минимально возможное значение $$$F$$$ при оптимальном выборе $$$x_i$$$ и $$$y_i$$$. Можно показать, что всегда существует хотя бы один корректный способ выбрать эти числа.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$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$$$.
105 02 0 1 3 45 15 3 4 3 57 27 6 5 4 3 2 15 11 2 3 4 55 21 2 3 4 54 00 1 1 15 54 3 5 6 44 10 2 1 03 99999200000 200000 2000006 81397976 129785 12984 78561 173685 15480
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$$$.
Название |
---|