# 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

The world of Mario can be imagined as 2D grid of N rows and M columns–containing a total of N × 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** (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 × M numbers follow indicating the power **P** (1 ≤ P ≤ 1000) of each cell. After that another N × M numbers follow indicating the points (|V| ≤ 100) of that cell.

### 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

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.

#### moinul.shaon

→