RSJ has a sequence $a$ of $n$ integers $a_1,a_2, \ldots, a_n$ and an integer $s$. For each of $a_2,a_3, \ldots, a_{n-1}$, he chose a pair of non-negative integers $x_i$ and $y_i$ such that $x_i+y_i=a_i$ and $(x_i-s) \cdot (y_i-s) \geq 0$.

Now he is interested in the value $$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.$$

Please help him find the minimum possible value $F$ he can get by choosing $x_i$ and $y_i$ optimally. It can be shown that there is always at least one valid way to choose them.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$, $s$ ($3 \le n \le 2 \cdot 10^5$; $0 \le s \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 2 \cdot 10^5$).

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the minimum possible value of $F$.


-----Examples-----

Input
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
Output
0
18
32
11
14
0
16
0
40000000000
2700826806


-----Note-----

In the first test case, $2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$.

In the second test case, $5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	k = [*map(int, input().split())]
	(fx, fy) = (0, 0)
	(px, py) = (k[0], k[0])
	for i in k[1:n - 1]:
		[x, y] = [0, i] if s > i else [i - s, s]
		(fx, fy) = (min(fx + py * x, fy + px * x), min(fx + py * y, fy + px * y))
		(px, py) = (x, y)
	print(min(fx + y * k[-1], fy + x * k[-1]))


def solve(n, s, a):
	f = lambda u, v, x: min(u[0] + u[1] * x, v[0] + v[1] * x)
	(lo, hi) = ((0, a[0]), (0, a[0]))
	for i in range(1, n - 1):
		(x1, x2) = (min(a[i], s), max(0, a[i] - s))
		(lo, hi) = ((f(lo, hi, x1), x2), (f(lo, hi, x2), x1))
	print(f(lo, hi, a[-1]))
t = int(input())
for test in range(t):
	(n, s) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	solve(n, s, a)


import sys
input = sys.stdin.readline

def solve():
	(n, s) = map(int, input().split())
	arr = list(map(int, input().split()))
	(x, y) = ([0] * n, [0] * n)
	for i in range(1, n - 1):
		a = s
		b = arr[i] - s
		if b <= 0:
			a += b
			b = 0
		x[i] = a
		y[i] = b
	dp = [[0, 0] for _ in range(n)]
	dp[1][0] = arr[0] * x[1]
	dp[1][1] = arr[0] * y[1]
	for i in range(2, n - 1):
		dp[i][0] = min(dp[i - 1][0] + x[i] * y[i - 1], dp[i - 1][1] + x[i] * x[i - 1])
		dp[i][1] = min(dp[i - 1][0] + y[i] * y[i - 1], dp[i - 1][1] + y[i] * x[i - 1])
	ans = min(dp[n - 2][0] + y[n - 2] * arr[n - 1], dp[n - 2][1] + x[n - 2] * arr[n - 1])
	print(ans)
t = int(input().strip())
for _ in range(t):
	solve()


def solve():
	(n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	x = [0] * (n + 1)
	y = [0] * (n + 1)
	for i in range(n):
		if s >= a[i]:
			x[i] = 0
			y[i] = a[i]
		else:
			x[i] = s
			y[i] = a[i] - s
	x[n - 1] = y[n - 1] = a[n - 1]
	x[0] = y[0] = a[0]
	dp = [[0 for _ in range(2)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		dp[i][0] = min(dp[i - 1][0] + x[i - 1] * y[i], dp[i - 1][1] + y[i - 1] * y[i])
		dp[i][1] = min(dp[i - 1][0] + x[i - 1] * x[i], dp[i - 1][1] + y[i - 1] * x[i])
	print(dp[n - 1][0])
T = int(input().strip())
for _ in range(T):
	solve()


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	l1 = [int(a) for a in input().split()]
	m1 = [0, l1[0]]
	m2 = [0, l1[0] + 1]
	for i in range(1, n - 1):
		if s <= l1[i]:
			l3 = [s, l1[i] - s]
		else:
			l3 = [0, l1[i]]
		n1 = m1[0] + m1[1] * l3[0]
		n2 = m2[0] + m2[1] * l3[0]
		if n1 < n2:
			k1 = [n1, l3[1]]
		else:
			k1 = [n2, l3[1]]
		l3.reverse()
		n1 = m1[0] + m1[1] * l3[0]
		n2 = m2[0] + m2[1] * l3[0]
		if n1 < n2:
			k2 = [n1, l3[1]]
		else:
			k2 = [n2, l3[1]]
		m1 = [int(a) for a in k1]
		m2 = [int(a) for a in k2]
	x1 = m1[0] + m1[1] * l1[-1]
	x2 = m2[0] + m2[1] * l1[-1]
	print(min(x1, x2))


for _ in range(int(input())):
	(n, s) = map(int, input().split(' '))
	nums = list(map(int, input().split(' ')))
	helpofx = [0] * n
	helpofy = [0] * n
	for i in range(1, n - 1):
		claci1 = s
		calci2 = nums[i] - s
		if calci2 <= 0:
			claci1 += calci2
			calci2 = 0
		(helpofx[i], helpofy[i]) = (claci1, calci2)
	precomputation = [[0] * 2 for _ in range(n)]
	(precomputation[1][0], precomputation[1][1]) = (nums[0] * helpofx[1], nums[0] * helpofy[1])
	for i in range(2, n - 1):
		precomputation[i][0] = min(precomputation[i - 1][0] + helpofx[i] * helpofy[i - 1], precomputation[i - 1][1] + helpofx[i] * helpofx[i - 1])
		precomputation[i][1] = min(precomputation[i - 1][0] + helpofy[i] * helpofy[i - 1], precomputation[i - 1][1] + helpofy[i] * helpofx[i - 1])
	print(min(precomputation[n - 2][0] + helpofy[n - 2] * nums[n - 1], precomputation[n - 2][1] + helpofx[n - 2] * nums[n - 1]))


from collections import defaultdict as dfd

def solve(N, S, nums):
	book = {nums[0]: 0}
	for i in range(1, N - 1):
		new = dfd(lambda : float('inf'))
		if nums[i] <= S:
			(a, b) = (0, nums[i])
		else:
			(a, b) = (S, nums[i] - S)
		for (n, s0) in book.items():
			s1 = s0 + n * a
			new[b] = min(new[b], s1)
			s1 = s0 + n * b
			new[a] = min(new[a], s1)
		book = new
	ans = float('inf')
	for (n, s0) in book.items():
		ans = min(ans, s0 + n * nums[-1])
	return ans
T = int(input())
for _ in range(T):
	(N, S) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	print(solve(N, S, nums))