Maximum Coins Collection

Maya is on a quest to collect as many coins as possible while traversing a grid. You are given a grid with N rows and M columns, where each cell contains a non-negative integer representing the number of coins at that cell. Maya starts at the upper-left corner (cell (1,1)) and must reach the bottom-right corner (cell (N,M)). She can only move right or down at each step.

Your task is to determine the maximum number of coins Maya can collect on her way. Formally, if we denote the number of coins at cell (i, j) as grid[i][j] then the recurrence for the dynamic programming solution can be written as:

$$dp[i][j] = grid[i][j] + \max\begin{cases} dp[i-1][j], & \text{if } i > 0 \\ dp[i][j-1], & \text{if } j > 0 \end{cases} $$

The answer will be found at dp[N-1][M-1] (using 0-indexing) or in other words, at the bottom-right cell.

You need to process multiple test cases. For each test case, you will be given the dimensions of the grid followed by the grid itself.

inputFormat

The first line of input contains a single integer T, the number of test cases. Each test case is described as follows:

• The first line contains two space-separated integers N and M.
• The next N lines each contain M space-separated integers, representing the rows of the grid.

outputFormat

For each test case, output a single line containing the maximum number of coins that Maya can collect on her path from the upper-left corner to the bottom-right corner.

## sample

4
3 4
1 2 3 4
0 1 2 1
4 0 1 1
2 2
1 2
1 3
2 2
0 0
0 0
2 2
1 1
1 1

12
6
0
3

</p>