Matrix Maximum Path Sum Problem

Given an N*M matrix filled with integer numbers, your task is to find the maximum path sum starting from any cell in the first row and ending at any cell in the last row. You can move downward, diagonally down to the left, or diagonally down to the right from any cell.

Example:

Input:

T = 1
N = 3, M = 3
Matrix: [[3, 2, 1], [5, 10, 7], [9, 6, 8]]

Output:

18

Explanation:

The path with the maximum sum is 3 -> 10 -> 9, which results in a sum of 18.

Constraints:

• 1 ≤ T ≤ 50
• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• -10^4 ≤ matrix[i][j] ≤ 10^4

Input:

The input will follow this format:

```
T
N M
Matrix rows
```

Output:

For each test case, you should output the maximum sum obtainable on a new line.

Note:

You are not required to print anything. The code should simply return the result.