950 . Pyramid Extreme
Description
It was so easy for Kelvin solving such a problem in a Pyramid (click here to see the origional problem), and he thought this two-level pyramid is too simple. So he decides to build more chambers inside the chambers in a pyramid. In a rectangle grid with R rows and C columns, each cell of this rectangle contains an integer. Kelvin wanted to choose 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. Kelvin then multiplies all the integers outside the first subrectangle with M0. Then he multiplies all the integers inside i-th rectangle but outside (i+1)-th rectangle with Mi. Then he multiples all the integers inside n-th subrectangle with Mn. So he get a new rectangle of integers. The sum of all the integers of this new rectangle is S. Help Kelvin to choose all this subrectangles in such a way so that S is maximized, and then he may go to play dota comfortably.
In the above example figure, the outer most portion (that is not contained in any of the sub rectangle) is multiplied by M0, the portion inside the first rectangle, but outside the second one by M1 (the grey area), portion inside 2nd and outside 3rd by M2, and so forth. The portion inside the N-th sub rectangle is multiplied by Mn (The white area inside the grey area).
Input Format
First line of the input contains T(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 R1,R2....,Rn(R>R1>R2>...>Rn). Third line contains n integers C1,C2,....,Cn(C>C1>C2>...>Cn). The values Ri, Ci describes the dimensions of the ith sub rectangle. Fourth line contains n+1 integers M0,M1,...,Mn (-10≤Mi≤10), the values of each multiplier. Lines 5 to line 4+R each contain C integers. The jth integer in the (i+4)th line is the number in the ith row and jth column of the initial rectangle. All the integers in the initial rectangle is between -100 to +100 inclusive.
Output Format
For each test case output contains one integer denoting the maximum value of S.
Sample Input 1
3 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 5 8 2 3 1 5 2 1 -1 2 1 5 10 3 7 1 2 5 6 12 4 4 3 3 1 5 2 4 3 1 6 6 19 8 1 1 1 3 4 2 4 5 6 6 3 3 3 2 2 2 5 8 2 3 1 5 2 0 1 0 1 5 10 3 7 1 2 5 6 12 4 4 3 3 1 5 2 4 3 1 6 6 19 8 1 1 1 3 4 2 4 5 6 6 3 3 3 2 2 2
Sample Output 1
22 120 71
Hints
Problem Source
Migrated from old NTUJ.
uva11263
Subtasks
| No. | Testdata Range | Score |
|---|