This Means War

An army is going into war, and the commander wants to divide all soldiers into groups so that their total strength is maximized. Treat the $N$ soldiers as points on the x-axis. All soldiers stand at distinct locations, and the $i$-th soldier stands at $x_i$. The soldiers are numbered from 1 to $N$ and are given sorted by their x values from left to right.

Divide the soldiers into one or more groups. Each soldier belongs to exactly one group, and every group is a contiguous block. A group $[a, b]$ with $a \le b$ contains soldiers $a$ through $b$ (inclusive), and no soldier from another group stands between them.

Each soldier $i$ has a function $f_i$. This function is used only when soldier $i$ is the leftmost soldier of its group. The strength of a group from position $a$ to position $b$ is $f_a(x_b)$: the value of $f_a$ at the x value of the rightmost soldier in the group.

You are given $M$ distinct sorted values $z_1, z_2, \dots, z_M$ and the values $f_i(z_j)$ for every function. For any $z$ other than these $M$ values, connect consecutive points $(z_j, f_i(z_j))$ with straight line segments. This defines each $f_i$ from $z_1$ to $z_M$.

The strength of the army is the sum of the strengths of all groups. Find the grouping that maximizes this sum.

The first line contains the number of test cases $T$ ($1 \le T \le 100$). Each test case is given as follows.

The first line contains two integers $N$ and $M$ ($1 \le N \le 10^5$, $2 \le M$, $N \times M \le 10^5$). The next line contains the sorted integers $x_1, x_2, \dots, x_N$ ($-10^6 \le x_i \le 10^6$). The next line contains the sorted integers $z_1, z_2, \dots, z_M$ ($-10^6 \le z_j \le 10^6$). The next $N$ lines each contain $M$ integers. The $j$-th integer on the $i$-th line is $f_i(z_j)$ ($-10^6 \le f_i(z_j) \le 10^6$).

It is guaranteed that $z_1 \le x_1$ and $x_N \le z_M$.

For each test case, print one line with the maximum strength of the army, rounded to exactly 6 decimal places.

The following image shows the first test case.

The 3 solid circles on the x-axis mark the locations of the 3 soldiers. The 3 functions $f_1$, $f_2$, and $f_3$ are plotted as described above, one for each soldier. The best solution puts the first 2 soldiers in one group and leaves the last soldier alone. The first group has strength $f_1(x_2)$, which is $f_1(2) = 4$. The last soldier's group has strength $f_3(x_3) = f_3(3) = 2.666667$. The total strength is therefore 6.666667 (rounded to 6 decimal places).