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 NN rows and MM columns--containing a total of N×MN \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 PP cells to the right or at most PP cells down. PP is the power of the cell Mario is currently in. Obviously Mario cannot go beyond the grid.

Each cell also has VV points in it. When Mario steps on a cell he gets the points from that cell. And, if VV is negative V|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 TT (0<T200 < T ≤ 20). Then T cases follow.

Each of the test case contains integers NN and MM (1N,M10001 ≤ N, M ≤ 1000) in the first line. Then N×MN \times M numbers follow indicating the power PP (1P10001 ≤ P ≤ 1000) of each cell. After that another N×MN \times M numbers follow indicating the points (V100|V| ≤ 100) of that cell.

Output

For each test case print a line Case x: y\texttt{Case x: y} where x\texttt{x} is the case number and y\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.

Discussion

Statistics


63% Solution Ratio

MohtasimEarliest, Nov '16

shahriarcsecu3Fastest, 0.3s

sahedsohelLightest, 16 MB

RobbinShortest, 1389B

Submit

Login to submit