Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

There is a straight road that passes through N short tunnels. At the entrance to the first tunnel, there are C cars lined up in a row waiting to enter the series of tunnels. The distance between each pair of consecutive tunnels is D metres (the lengths of each tunnel and each car are negligible) and the velocity of each car is S metres per second.

Each tunnel contains a toll booth. In the i-th tunnel (1 ≤ i ≤ N), processing a car at the toll booth takes A_{i} seconds. Only one car can be processed at the same time. If there are multiple cars in the tunnel, they all have to wait for the first car to be processed; afterwards, the first car exits the tunnel, the second car starts being processed and all remaining cars have to wait again, etc. Whenever a car arrives in a tunnel, it has to wait at that tunnel's toll booth until all previous cars have been processed and then get processed itself.

The road and the tunnels are too narrow, so cars can't overtake each other at any time during the journey.

Chef is after Reziba once again. Reziba's car is the first car to enter the tunnels, while Chef's car is the last car to enter the tunnels.

Compute the final delay (in seconds) between the first (Reziba's) car and the last (Chef's) car immediately after Chef's car exits the last tunnel, i.e. after all the cars have passed through the tunnels. This delay is equal to the distance between the first and the last car divided by the cars' velocity, or equivalently to the difference between the times when the last car and the first car exit the last tunnel.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of tunnels.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the time taken for processing a car at each toll booth.
The third line contains three space-separated integers C, D and S.

------ Output ------ 

For each test case, print a single line containing one real number — the time delay between the first and last car after all the cars have passed through all the tunnels. Your answer will be considered correct if its absolute error is less than 10^{-6}.

------ Constraints ------ 

1 ≤ T ≤ 100
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{9} for each valid i
2 ≤ C ≤ 10^{6}
1 ≤ D, S ≤ 10^{9}

------ Subtasks ------ 

Subtask #1:
1 ≤ N ≤ 1,000
C = 2
Subtask #2: Original Constraints

----- Sample Input 1 ------ 
2
3
2 2 2
3 5 5
2
3 2
2 1 1
----- Sample Output 1 ------ 
4.000000000
3.000000000
----- explanation 1 ------ 
Example case 1: Each car takes 5/5 = 1 second to go from one tunnel to the next tunnel.

Since each car has to wait for equally long (2 seconds) in each tunnel, the delay between every two consecutive cars exiting each tunnel is 2 seconds.

As there are 3 cars, the total time delay between the first and the last car after the last tunnel is 4 seconds.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	print((c - 1) * max(a))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	print(c * max(l) - max(l))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		n = nl()
		a = ln()
		(c, d, s) = sm()
		print(max(a) * (c - 1))
main()


def lisin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = input()
	a = lisin()
	(c, d, s) = lisin()
	print((c - 1) * max(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(b, c, d) = map(int, input().split())
	print(max(a) * (b - 1))


for _ in range(int(input())):
	input()
	times = map(int, input().split())
	C = int(input().split()[0])
	print((C - 1) * max(times))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	m = max(a)
	ans = m * (c - 1)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(s) for s in input().split()]
	(C, D, S) = [int(s) for s in input().split()]
	maxA = float(max(A)) * (C - 1)
	print(f'{maxA:.9f}')


t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	m = max(a)
	sum = m * (c - 1)
	print(sum)


tc = int(input())
for _ in range(tc):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	sum = 0.0
	sum = float(max(l1) * (l2[0] - 1))
	print(f'{sum:.9f}')


t = int(input())
for _ in range(t):
	n = int(input())
	time = list(map(int, input().split()))
	(cars, d, s) = map(int, input().split())
	maximum = max(time)
	print('{:.9f}'.format(maximum * (cars - 1)))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	print(max(ls) * (c - 1))


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	(C, D, S) = [int(i) for i in input().split()]
	ans.append(max(A) * (C - 1))
for i in ans:
	print(i)


t = int(input())
for testcase in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(C, D, S) = list(map(int, input().split()))
	x = (C - 1) * max(a) + sum(a)
	time = x - sum(a)
	print(time)


tc = int(input())
for ii in range(tc):
	n = int(input())
	ar = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	x = max(ar)
	ans = x * (c - 1)
	print('%.9f' % ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	(c, d, s) = map(int, input().split())
	print(m * (c - 1))


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(C, D, S) = map(int, input().split())
	delay = 0
	if C == 2:
		delay = max(A)
	else:
		delay = max(A) * (C - 1)
	print(delay)


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	(C, D, S) = list(map(int, input().split()))
	print(max(a) * (C - 1))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = map(int, input().split())
	(c, d, s) = map(int, input().split())
	print((c - 1) * max(a))


for _ in range(int(input())):
	n = int(input())
	arr = [int(y) for y in input().split()]
	(c, d, s) = [int(y) for y in input().split()]
	ci = 0
	d = []
	for x in range(n):
		d.append(arr[x] + ci)
		ci = d[x]
	d1 = arr[0] * 2
	for x in range(1, n):
		d1 = max(d1, d[x]) + arr[x]
	print((d1 - d[n - 1]) * (c - 1))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(c, d, s) = [int(i) for i in input().split()]
	ans = max(a)
	print(ans * (c - 1))


t = int(input())
while t:
	n = int(input())
	a = [float(x) for x in input().split()]
	c = int(input().split()[0])
	print((c - 1) * max(a))
	t -= 1


for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	print(max(A) * (c - 1))


t = int(input())
for itr in range(0, t):
	n = int(input())
	a = input().split()
	for i in range(0, n):
		a[i] = int(a[i])
	r = input().split()
	c = int(r[0])
	d = int(r[1])
	s = int(r[2])
	delay = max(a)
	ans = delay * (c - 1)
	print(ans)


t = int(input())
for U in range(t):
	no_of_tolls = int(input())
	toll_time = [int(i) for i in input().split()]
	(C, D, S) = [int(j) for j in input().split(' ')]
	max_tolltime = max(toll_time)
	print((C - 1) * max_tolltime)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	q = max(l)
	print(float((c - 1) * q))


for _ in range(int(input())):
	n = int(input())
	a = []
	a = [int(k) for k in input().split()]
	(c, d, s) = [int(k) for k in input().split()]
	print(str(max(a) * (c - 1)))


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	c = max(b)
	d = [int(i) for i in input().split()]
	print(c * (d[0] - 1))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	tot_car = c - 1
	max_time = max(a)
	answer = tot_car * max_time
	print(format(answer, '.9f'))


def main():
	t = int(input())
	while t > 0:
		n = int(input())
		a = [int(i) for i in input().split()]
		[c, d, s] = [int(i) for i in input().split()]
		print(float((c - 1) * max(a)))
		t = t - 1
main()


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	maxBoothTime = max(A)
	prevCars = c - 1
	timeDiff = prevCars * maxBoothTime
	print('{0:.9f}'.format(timeDiff))


for _ in range(int(input())):
	number_of_tunnels = int(input())
	tunnel_time_list = [int(x) for x in input().split()]
	(cars, distance_between, speed) = map(int, input().split())
	m = max(tunnel_time_list)
	print('{0:.9f}'.format(m * (cars - 1)))


for t in range(int(input())):
	n = int(input())
	ans = max([int(i) for i in input().split()])
	c1 = [int(i) for i in input().split()][0]
	time = float((c1 - 1) * ans)
	print('%11.9f' % time)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	v = d // s
	tm = n * [0]
	tmp = 0
	tm[0] = ar[0]
	(a1, ap, ab) = (ar[0], 0, 0)
	(b1, bp, bb) = (2 * ar[0], 0, 0)
	for i in range(1, n):
		ap = a1 + v
		ab = ap + ar[i]
		bp = b1 + v
		if ab > bp:
			tmp = ab - bp
			bb = ab + ar[i]
		else:
			tmp = 0
			bb = bp + ar[i]
		tm[i] = tmp
		a1 = ab
		b1 = bb
	ans = 0
	ans = sum(tm) * (c - 1)
	print(format(ans, '.9f'))


t = int(input())
for k in range(t):
	n = float(input())
	a = list(map(float, input().split()))
	(c, d, s) = map(float, input().split())
	print(max(a) * (c - 1))


for tc in range(int(input())):
	N = int(input())
	a = [int(x) for x in input().split()]
	max_a = max(a)
	cds = [int(x) for x in input().split()]
	C = cds[0]
	D = cds[1]
	S = cds[2]
	delay = float((C - 1) * max_a)
	print('%f' % delay)
	print()


t = int(input())
while t:
	n = int(input())
	arr = input().split()
	(c, d, s) = input().split()
	maxi = -1000
	for i in range(n):
		if maxi < int(arr[i]):
			maxi = int(arr[i])
	ans = maxi * (int(c) - 1)
	print('%.9f' % ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	toll_booth = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	ttb1 = ttb2 = 0
	for i in toll_booth:
		ttb1 += i
		ttb2 = max(ttb1, ttb2) + i
	print((ttb2 - ttb1) * (c - 1))


test = int(input())
while test > 0:
	tolls = int(input())
	tolltime = list(map(int, input().split()))
	(c, d, v) = map(int, input().split())
	i = 0
	delay = max(tolltime)
	print('{:.9f}'.format(delay * (c - 1)))
	test -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	second_car_delay = a[0]
	for s in range(1, len(a)):
		if a[s] > second_car_delay:
			second_car_delay = a[s]
	final_time = second_car_delay * (b[0] - 1)
	print('%.9f' % final_time)


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	mn = max(ls)
	(a, b, c) = map(int, input().split())
	print(format((a - 1) * mn, '.9f'))


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	(c, d, s) = tuple(map(int, input().split()))
	print('{0:.9f}'.format((c - 1) * m))


for tc in range(int(input())):
	N = int(input())
	max_a = max([int(x) for x in input().split()])
	C = [int(x) for x in input().split()][0]
	delay = float((C - 1) * max_a)
	print('%11.9f' % delay)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(float, input().split()))
	(c, d, s) = list(map(float, input().split()))
	print(max(arr) * (c - 1))


for _ in range(int(input())):
	n = int(input())
	maxWait = max([int(i) for i in input().split()])
	c = [int(i) for i in input().split()][0]
	ans = float((c - 1) * maxWait)
	print(ans)


T = int(input())
ans = []
for i in range(T):
	N = int(input())
	A = input().strip().split(' ')
	tun = list(map(int, A))
	o = input().strip().split(' ')
	C = int(o[0])
	D = int(o[1])
	S = int(o[2])
	ans.append(max(tun) * (C - 1))
for i in range(T):
	print(ans[i])


t = int(input())
for q in range(t):
	sum = 0
	n = int(input())
	m = list(map(int, input().split()))
	m.sort()
	k = m[len(m) - 1]
	l = list(map(int, input().split()))
	j = l[0]
	f = k * (j - 1)
	print('%.9f' % f)


import sys
testcase = int(input())
while testcase:
	testcase -= 1
	n = int(input())
	a = list(map(int, sys.stdin.readline().split()))
	(c, d, s) = map(int, sys.stdin.readline().split())
	t1 = 0.0
	tc = 0.0
	t1 = a[0]
	t2 = 2 * a[0]
	tc = c * a[0]
	for i in range(1, n):
		t1 += a[i]
		if t1 > t2:
			t2 = t1 + a[i]
			tc = t1 + (c - 1) * a[i]
		else:
			t2 += a[i]
			tc += a[i]
	print(float(tc - t1))


for tc in range(int(input())):
	N = int(input())
	a = [int(x) for x in input().split()]
	max_a = max(a)
	cds = [int(x) for x in input().split()]
	A = cds[0]
	B = cds[1]
	C = cds[2]
	dela = float((A - 1) * max_a)
	print('%11.9f' % dela)
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	c -= 1
	print('{0:.9f}'.format(max(arr) * c))


t = int(input())
for z in range(t):
	n = int(input())
	timetaken = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	print(max(timetaken + [0]) * (c[0] - 1))


t = int(input())
for ii in range(t):
	n = int(input())
	time = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	maxa = time[0]
	wt = (c - 1) * time[0]
	for i in range(1, n):
		if time[i] > maxa:
			wt += (c - 1) * (time[i] - maxa)
			maxa = time[i]
	print('%.9f' % wt)


for t in range(int(input())):
	k = input()
	N = int(k)
	cc = input().split()
	ma = max([int(x) for x in cc])
	C = [int(x) for x in input().split()][0]
	ans = float((C - 1) * ma)
	print('%11.9f' % ans)


trial = int(input())
for trial_cnt in range(trial):
	n = int(input())
	max_time = max(list(map(int, input().split())))
	(c, d, s) = list(map(int, input().split()))
	print(max_time * (c - 1))


for numOfTests in range(int(input())):
	NumberofTollBooths = int(input())
	MaxProcessingTimeOfTollBooths = max([int(x) for x in input().split()])
	numOfCars = [int(x) for x in input().split()][0]
	totalDelay = float((numOfCars - 1) * MaxProcessingTimeOfTollBooths)
	print('%11.9f' % totalDelay)


t = input()
t = int(t)
for x in range(t):
	n = int(input())
	ntime = list(map(int, input().split()))
	rtime = list(map(int, input().split()))
	c = rtime[0]
	p = max(ntime)
	m = p * (c - 1)
	print('{0:.9f}'.format(m))


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = [int(x) for x in input().strip().split(' ')]
	(c, d, s) = [int(x) for x in input().strip().split(' ')]
	l1 = list(a)
	l1.sort()
	k = 0
	for i in range(n - 1):
		k += (c - 1) * (l1[i + 1] - l1[i])
	print('%.9f' % (k + (c - 1) * l1[0]))


t = int(input())
tunnel = []
time = []
inp = []
out = []
for a in range(t):
	n = int(input())
	tunnel.append(n)
	ti = input()
	time.append(ti)
	s = input()
	inp.append(s)
for a in range(t):
	entry = inp[a]
	(c, d, s) = entry.strip().split(' ')
	c = int(c)
	d = int(d)
	s = int(s)
	time_arr = time[a].strip().split(' ')
	for a in range(len(time_arr)):
		time_arr[a] = float(time_arr[a])
	max_time = float(max(time_arr))
	res = (c - 1) * max_time
	res = format(res, '.9f')
	out.append(res)
for q in out:
	print(q)


z = int(input())
for _ in range(z):
	n = int(input())
	arr = [int(x) for x in input().split()]
	(c, d, s) = map(int, input().split())
	v1 = []
	v2 = []
	t = 0
	ts = d / s
	for i in range(n):
		v1.append(t)
		t += arr[i]
	t = 0
	for i in range(n):
		if t >= v1[i] and t < v1[i] + arr[i]:
			temp = v1[i] + arr[i]
			v2.append(temp)
			t = temp + arr[i]
		else:
			v2.append(t)
			t = t + arr[i]
	print('%.9f' % ((c - 1) * (v2[len(v2) - 1] - v1[len(v1) - 1])))


T = int(input())
while T:
	N = int(input())
	A = list(map(int, input().split()))
	(C, D, S) = map(int, input().split())
	print((C - 1) * max(A))
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().strip().split(' ')))
	l2 = list(map(int, input().strip().split(' ')))
	c = l2[0]
	ans = (c - 1) * l1[0]
	m = l1[0]
	for j in range(1, n):
		if l1[j] > m:
			ans = ans + (l1[j] - m) * (c - 1)
			m = l1[j]
	print(ans)


t = int(input())
for i in range(t):
	q = int(input())
	x = [int(x) for x in input().split()]
	y = [int(x) for x in input().split()]
	out = (y[0] - 1) * max(x)
	print(out)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(c, d, s) = map(int, input().split())
	wait = a[0] * (c - 1)
	xtra = 0
	for i in range(1, n):
		if xtra + a[i - 1] <= a[i]:
			wait += (a[i] - a[i - 1] - xtra) * (c - 1)
			xtra = 0
		elif a[i - 1] > a[i]:
			xtra += a[i - 1] - a[i]
		elif xtra + a[i - 1] > a[i]:
			xtra -= a[i] - a[i - 1]
	print('{:.9f}'.format(float(wait)))