Maximum Path Sum

You are given a grid with n rows and m columns containing integer values. Starting from the top-left cell of the grid, your task is to compute the maximum sum obtainable by travelling to the bottom-right cell. At each step, you can only move either to the right or downward.

The problem can be mathematically expressed as follows: Let \(dp[i][j]\) denote the maximum sum obtainable reaching cell \((i, j)\). Then, the recurrence is:

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

with the initial conditions \(dp[0][0] = grid[0][0]\), \(dp[i][0] = dp[i-1][0] + grid[i][0]\) for \(i > 0\), and \(dp[0][j] = dp[0][j-1] + grid[0][j]\) for \(j > 0\).

Your solution should be efficient enough to handle large grids under typical contest constraints.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains two space-separated integers \(n\) and \(m\), representing the number of rows and columns of the grid respectively.
• This is followed by \(n\) lines, each containing \(m\) space-separated integers representing the grid.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single integer representing the maximum sum obtainable by moving from the top-left to the bottom-right of the grid (only moving right or down). Each answer should be printed on a new line on standard output (stdout).

## sample

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

29
1
15

</p>