The world of Mario can be imagined as 2D grid of rows and columns--containing a total of 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 cells to the right or at most cells down. is the power of the cell Mario is currently in. Obviously Mario cannot go beyond the grid.
Each cell also has points in it. When Mario steps on a cell he gets the points from that cell. And, if is negative 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.
The first line contains the number of test cases (). Then T cases follow.
Each of the test case contains integers and () in the first line. Then numbers follow indicating the power () of each cell. After that another numbers follow indicating the points () of that cell.
For each test case print a line where is the case number and is the maximum points Mario can get while rescuing Princess Peach.
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.