Mario's Coin Collection

Mario loves to explore his castle in search of coins. The castle is represented as a grid of size \(R \times C\). Mario starts at the top-left cell, \((0,0)\), and his goal is to reach the bottom-right cell, \((R-1, C-1)\). At each cell, Mario collects the coins present there. He can only move right or down at each step. Your task is to determine the maximum number of coins Mario can collect on his way.

Note: The value in each grid cell represents the number of coins at that cell.

The problem can be formulated using the following recurrence:

[ \text{dp}[i][j] = \text{grid}[i][j] + \max\left(\begin{array}{l} \text{dp}[i-1][j] \ \text{dp}[i][j-1] \end{array}\right) ]

with base case \(\text{dp}[0][0] = \text{grid}[0][0]\).

inputFormat

The input is read from stdin and has the following format:

T
R C
row1_element1 row1_element2 ... row1_elementC
... (R rows in total)
... (T test cases in total)

Where:

• T - the number of test cases.
• R and C - the number of rows and columns in the grid respectively.
• Each of the next R lines contains C integers representing the grid.
</p>

outputFormat

For each test case, output a single line to stdout containing the maximum number of coins Mario can collect.

## sample

1
3 3
0 1 0
1 0 1
0 1 1

3

</p>