BRII - Bridges! More bridges!

no tags 

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
a0 a1 a2 ... an
h1 h2 ... hn
c
s0 s1 s2 ... sn

Here n is the number of the rivers which are parallel to each other, ai - the distances between rivers or between rivers and cities, hi - the widths of the rivers, c - the distance between A and B along the axis parallel to the river, si - the costs of the unit of the bridge through ith river and s0 - 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


Added by:Ruslan Sennov
Date:2009-10-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL NODEJS PERL6 VB.NET
Resource:BRIDGE