Problem BRIDGE has shown that you are able to build the cheap bridge through the river very quickly. Now you will not have problems with time limit. You will have problems with number of bridges.

Input

There is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case is exactly five lines, containing description of the route between two cities A and B, located on opposite sides of the rivers.

n
a₀ a₁ a₂ ... a_n
h₁ h₂ ... h_n
c
s₀ s₁ s₂ ... s_n

Here n is the number of the rivers which are parallel to each other, a_i - the distances between rivers or between rivers and cities, h_i - the widths of the rivers, c - the distance between A and B along the axis parallel to the river, s_i - the costs of the unit of the bridge through i_th river and s₀ - the cost of the unit of the road. Example for n=2 you can see on the picture.

All integers in input are positive and less than 50, except c - it is less than 2000.

Output

For each test case your program should write a single number to the standard output, equal to the minimal total cost of the route between A and B, accurate up to two digits after the decimal dot.

Example

Input:
1
2
1 1 1
1 1
1
1 1 1

Output:
5.10