The world of Mario can be imagined as 2D grid of $N$
rows and $M$
columns--containing a total of $N \times M$
cells. Mario starts from the top-leftmost cell and Princess Peach is located at the bottom-rightmost cell.
In each step, Mario can jump at most $P$
cells to the right or at most $P$
cells down. $P$
is the power of the cell Mario is currently in. Obviously Mario cannot go beyond the grid.
Each cell also has $V$
points in it. When Mario steps on a cell he gets the points from that cell. And, if $V$
is negative $|V|$
points are deducted.
As you are a programmer, you want to find out what can be the maximum collected points in a given grid if the player plays in an optimal way.
The first line contains the number of test cases $T$
($0 < T ≤ 20$
). Then T cases follow.
Each of the test case contains integers $N$
and $M$
($1 ≤ N, M ≤ 1000$
) in the first line. Then $N \times M$
numbers follow indicating the power $P$
($1 ≤ P ≤ 1000$
) of each cell. After that another $N \times M$
numbers follow indicating the points ($|V| ≤ 100$
) of that cell.
For each test case print a line $\texttt{Case x: y}$
where $\texttt{x}$
is the case number and $\texttt{y}$
is the maximum points Mario can get while rescuing Princess Peach.
Input | Output |
---|---|
2 3 3 3 3 2 2 3 2 1 1 2 3 -10 6 -1 2 -8 4 3 2 3 3 3 3 2 2 3 2 1 1 2 3 -5 7 -1 2 -3 2 4 1 | Case 1: 12 Case 2: 11 |
The data set is huge. Please use fast I/O methods.