Maximum Path Sum in a Grid

Given a grid of integers with dimensions (n \times m), your task is to determine the maximum sum path from the top-left corner to the bottom-right corner. You are only allowed to move either right or down at any step. The problem can be formulated using dynamic programming with the recurrence relation: (dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j]). This formula computes the maximum path sum reaching cell ( (i, j) ). Read the input from stdin and output the result for each test case to stdout.

inputFormat

The first line of input contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m), where (n) is the number of rows and (m) is the number of columns. This is followed by (n) lines each with (m) integers, representing the grid. All input is provided via stdin.

outputFormat

For each test case, output a single line containing the maximum sum obtainable along a valid path from the top-left cell to the bottom-right cell. The output for each test case is sent to stdout.## sample

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

29
-7