18697번 - This Means War 다국어

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_i on the 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 defined using 2 integers, a and b (where a ≤ b), which means this group includes all soldiers from the a-th position to the b-th position (inclusive).

Each soldier will be given a function fi 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 different values, each value is z_j (they are numbered from 1 to M), which will be used to evaluate all the functions, for each function f_i you will be given the value of f_i(z_j). To get the value of any z other than the given M ones, you just consider (z_j, f_i(z_j)) as a point, and connect every 2 consecutive points (based on z_j) in each function using a straight line segment, and now you have a function which covers all possible values from z₁ to 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-th position is fa(xb), in other words, it’s the value of the function for the left most soldier when we pass the x value of the right most soldier to it. Check the notes at the end for more explanation of the first 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 first line of the input will be a single integer T (1 ≤ T ≤ 100) 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⁵) representing the number of soldiers and M (2 ≤ M, N × M ≤ 10⁵) representing the number of z values.

Followed by a line containing N sorted integers separated by a space, which are the positions of the soldiers x₁, x₂, . . . , x_N (-10⁶ ≤ x_i ≤ 10⁶).

Followed by a line containing M sorted integers separated by a space, which are the z values as described above z₁, z₂, . . . , z_M (-10⁶ ≤ z_j ≤ 10⁶).

Followed by N lines, each line contains M integers separated by a space. The j-th value from the left in the i-th line from the top is the value of f_i(z_j) (-10⁶ ≤ f_i(z_j) ≤ 10⁶).

It’s guaranteed that z₁ ≤ x₁ 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.

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₁, f₂ and f₃ (one for each soldier) plotted as described above. The best solution here is to put the first 2 soldiers in a group, the strength of that group will be f₁(x₂), which is f₁(2) = 4, and the last soldier alone and the strength of that group will be f₃(x₃),which is f₃(3) = 2 .666667, so the total strength is 6.666667 (everything rounded to 6 decimal places).