Maximum Path Sum in a Matrix

You are given a matrix of integers. Your task is to find a path from the top-left cell to the bottom-right cell such that the sum of all numbers along the path is maximized. You can only move either to the right or down at any point in time.

The problem can be formulated using dynamic programming. Let (dp[i][j]) be the maximum sum to reach cell ((i, j)). The recurrence is given by:
[ dp[i][j] = \max(dp[i-1][j],, dp[i][j-1]) + A[i][j] ]

Compute (dp[m-1][n-1]) where (m) and (n) are the number of rows and columns of the matrix, respectively. You need to process multiple test cases provided via standard input.

inputFormat

The first line contains an integer (T) denoting the number of test cases. For each test case, the first line contains two integers (M) and (N) representing the number of rows and columns. This is followed by (M) lines each containing (N) space-separated integers corresponding to the matrix elements.

outputFormat

For each test case, output a single line containing the maximum path sum from the top-left to the bottom-right cell.## sample

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

29
30
16