An army is going into war, and they want to divide all soldiers into some groups, in a way that maximizes their total strength. Let’s consider the *N* soldiers as points in a 2-dimensional plane, with all soldiers standing on the *x*-axis at distinct locations, the *i ^{th}* soldier will be standing at

*x*on the

_{i}*x*-axis (the soldiers are numbered from 1 to

*N*). You will be given the soldiers in a sorted order based on their

*x*value, from left to right.

Your task is to divide them into one or more groups, where each soldier belongs to exactly one group, and all members of any group are next to each other without anyone else from other groups in between them, so each group will be deﬁned using 2 integers, *a* and *b* (where *a ≤ b*), which means this group includes all soldiers from the *a ^{th}* position to the

*b*position (inclusive).

^{th}
Each soldier will be given a function *f _{i}* to be used (only if that soldier is the left most soldier of a group) to evaluate the strength of the group. You will be given a list of

*M*diﬀerent values, each value is

*z*(they are numbered from 1 to

_{j}*M*), which will be used to evaluate all the functions, for each function

*f*you will be given the value of

_{i}*f*. To get the value of any

_{i}(z_{j})*z*other than the given

*M*ones, you just consider

*(z*as a point, and connect every 2 consecutive points (based on

_{j}, f_{i}(z_{j}))*z*) in each function using a straight line segment, and now you have a function which covers all possible values from

_{j}*z*to

_{1}*z*.

_{M}
The strength of the whole army is the sum of strengths of each group, the strength of a group from the *a ^{th}* position to the

*b*position is

^{th}*f*, in other words, it’s the value of the function for the left most soldier when we pass the

_{a}(x_{b})*x*value of the right most soldier to it.

**Check the notes at the end for more explanation of the ﬁrst test case.**

You are given all the required details as described above, and your task is to divide the soldiers into groups to maximize the total strength of the whole army.

Your program will be tested on one or more test cases. The ﬁrst line of the input will be a single integer *T (1 ≤ T ≤ 10)* representing the number of test cases. Followed by *T* test cases.

Each test case starts with a line containing 2 integers separated by a space, *N (1 ≤ N ≤ 10 ^{5})* representing the number of soldiers and

*M (2 ≤ M, N×M ≤ 10*representing the number of

^{5})*z*values.

Followed by a line containing *N* sorted integers separated by a space, which are the positions of the soldiers *x _{1}, x_{2}, ..., x_{N} (-10^{6} ≤ x_{i} ≤ 10^{6})*.

Followed by a line containing *M* sorted integers separated by a space, which are the *z* values as described above *z _{1}, z_{2}, ..., z_{M} (-10^{6} ≤ z_{j} ≤ 10^{6})*.

Followed by *N* lines, each line contains *M* integers separated by a space. The *j ^{th}* value from the left in the

*i*line from the top is the value of

^{th}*f*

_{i}(z_{j}) (-10^{6}≤ f_{i}(z_{j}) ≤ 10^{6}).
It is guaranteed that *z _{1} ≤ x_{1}* and

*x*

_{N}≤ z_{M}.

For each test case print a single line containing a single decimal number rounded to exactly 6 decimal places, which is the maximum strength of the whole army you can get.

3 3 4 -5 2 3 -6 1 4 5 -1 3 6 0 2 -2 -4 -6 -4 0 4 5 5 2 -2 5 8 9 10 -2 10 -7 -6 -3 -7 0 -8 9 -10 5 -4 2 2 0 7 -2 7 -10 -2 -4 -10

6.666667 -6.000000 -2.000000

The following image represents the first test case:

The 3 solid circlers on the *x*-axis are the locations of the 3 soldiers, and we have the 3 functions *f _{1}, f_{2}* and

*f*(one for each soldier) plotted as described above. The best solution here is to put the ﬁrst 2 soldiers in a group, the strength of that group will be

_{3}*f*, which is

_{1}(x_{2})*f*, and the last soldier alone and the strength of that group will be

_{1}(2) = 4*f*, which is

_{3}(x_{3})*f*, so the total strength is 6.666667 (everything rounded to 6 decimal places).

_{3}(3) = 2.666667- 5 seconds
- 256MB

**Problem source:** A2OJ