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

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 |

Huge input file, avoid slower input methods.

#### moinul.shaon

→