# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Mario and Princess Peach

By moinul.shaon · Limits 2s, 512 MB

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.

## Input

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.

## Output

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.

## Sample

InputOutput
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.

### Statistics

63% Solution Ratio

MohtasimEarliest, Nov '16

shahriarcsecu3Fastest, 0.3s

sahedsohelLightest, 16 MB

RobbinShortest, 1389B