Maximum Coin Value Path

You are given a grid of size m x n where each cell contains an integer coin value. Your task is to find the maximum sum of coin values that can be collected if you start at the top-left corner and move to the bottom-right corner.

You can only move either right or down at any step. Formally, if you denote dp[i][j] as the maximum coin value that can be collected upon reaching cell (i, j), then the recurrence relation is given by:

\( dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + grid[i][j] \)

with the base case being dp[0][0] = grid[0][0]. Your solution should process input from stdin and output the result to stdout for each test case.

inputFormat

The input is given via stdin in the following format:

T
m n
row1 (n space separated integers)
row2
...
row m

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers m and n, denoting the number of rows and columns respectively.
• The next m lines describe the grid with each line containing n space-separated integers.

outputFormat

For each test case, output a single integer on a new line representing the maximum coin value that can be collected from the top-left to the bottom-right cell.

## sample

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

12