Maximum Sum Path in a Matrix

You are given an n × m matrix of integers. Your task is to compute the maximum sum of a path from the top-left cell (i.e. cell at position (0,0)) to the bottom-right cell (i.e. cell at position (n-1, m-1)). At each step, you are allowed to move either right or down only.

The solution involves using dynamic programming. Let \( dp[i][j] \) denote the maximum sum obtainable when reaching cell \( (i,j) \). The recurrence is given by:

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

with the initial conditions:

• \( dp[0][0] = matrix[0][0] \)
• For the first row: \( dp[0][j] = dp[0][j-1] + matrix[0][j] \)
• For the first column: \( dp[i][0] = dp[i-1][0] + matrix[i][0] \)

Output the value of \( dp[n-1][m-1] \) for each test case.

inputFormat

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

T
n1 m1
matrix_row_1
matrix_row_2
...
matrix_row_n1
n2 m2
matrix_row_1
matrix_row_2
...
matrix_row_n2
...

Here, T denotes the number of test cases. For each test case, the first line contains two integers n and m (the number of rows and columns, respectively). This is followed by n lines each containing m space-separated integers representing the matrix.

outputFormat

For each test case, output a single integer — the maximum sum of a valid path from the top-left to the bottom-right cell. Each result should be printed on its own line to standard output (stdout).

## sample

2
3 3
1 2 3
4 5 6
7 8 9
3 4
1 2 3 4
-1 -2 -3 -4
2 1 -2 -1

29
5

</p>