Problem D
Nested Rectangles
Input: Standard Input

Output: Standard Output

Sultan has a rectangle of R rows and C columns. Each cell of this rectangle contains an integer. Sultan chooses n subrectangles. The i’th subrectangle has Ri rows and Ci columns and it is nested inside (i-1)’th subrectangle. The first subrectangle is nested inside the initial rectangle. Sultan then multiplies all the integers outside the first subrectangle with M₀. Then he multiplies all the integers inside i’th rectangle but outside (i+1)’th rectangle with M_i. Then he multiples all the integers inside n’th subrectangle with M_n. So he get a new rectangle of integers. The sum of all the integers of this new rectangle is S. Help Sultan to choose all this subrectangles in such a way so that S is maximized.

-1	-1	-1	-1	-1	-1
-1	2	2	2	-1	-1
-1	2	-1	2	-1	-1
-1	2	-1	2	-1	-1
-1	2	2	2	-1	-1
-1	-1	-1	-1	-1	-1

In the above figure, the outer most portion (that is not contained in any of the sub rectangle) is multiplied by M₀, the portion inside the first rectangle, but outside the second one by M₁, portion inside 2^nd and outside 3^rd by M₂, and so forth. The portion inside the N th sub rectangle is multiplied by M_n.

Input:

First line of the input contains T(≤20) the number of test cases. First line of the each test case contains 3 integers R(1≤R≤500),C(1≤C≤500) and n(1≤n≤5). Second line contains n integers R₁,R₂....,R_n(R> R_1>R₂>...>R_n). Third line contains n integers C₁,C₂,....,C_n(C> C₁>C₂>...>C_n). The values R_i, C_i describes the dimensions of the i^th sub rectangle. Fourth line contains n+1 integers M₀,M₁,...,M_n (-10≤M_i≤10), the values of each multiplier. Lines 5 to line 4+R each contain C integers. The j^th integer in the (i+4)^th line is the number in the i^th row and j^th column of the initial rectangle. All the integers in the initial rectangle is between -100 to +100 inclusive.

Output:

For each test case output contains one integer denoting the maximum value of S.

Sample Input	Sample Output
1 6 6 2 4 2 3 1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 2 -1 -1 -1 2 -1 2 -1 -1 -1 2 -1 2 -1 -1 -1 2 2 2 -1 -1 -1 -1 -1 -1 -1 -1	22

---

Problemsetter: Abdullah Al Mahmud

Special Thanks To: Manzurur Rahman Khan