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

Limits: 2s, 512 MB

The world of Mario can be imagined as 2D grid of row N and column M containing a total of N×M cell. Mario starts from top-leftmost cell and Princess Peach is located at bottom-rightmost cell.

In each step, Mario can jump at most P cell right or at most P cell down, where P is the power of the cell Mario is located. Obviously Mario cannot go beyond the grid. Each cell has V points located in it. When Mario steps on a cell he gets the points located in that cell (if V is negative |V| points is deducted). As you are a programmer, you want to find out what can be the maximum collected points in a given grid if player plays in an optimal way.

Input

The first line contains the number of test cases, T (T ≤ 20). Then T cases follow. Each of the test case contains N, M (1 ≤ N, M ≤ 1000) in the first line. Then N×M numbers follow showing the power of each cell (|V| <= 100). After that another N×M numbers follow showing the points of that cell.

Limits:

T ≤ 20; 1 ≤ N, M ≤ 1000; 1 ≤ P ≤ 1000; |V| ≤ 100

Output

For each test case print a line “Case x: y” where x is the case number and y is the maximum points Mario can get while rescuing Princess Peach

Samples

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

Huge input file, avoid slower input methods.

Author
  • moinul.shaon's Avatar

    moinul.shaon

Discussion
Submit

Login to submit