Maximum Path Sum in Grid

You are given a grid of integers with ( n ) rows and ( m ) columns. Starting from any cell in the first row, your task is to find a path to any cell in the last row such that the sum of the values along the path is maximized. At each step, you may move from cell ((i, j)) to one of the cells ((i+1, j-1)), ((i+1, j)), or ((i+1, j+1)), provided that the destination cell exists in the grid.

The formulation can be summarized as finding the maximum value of: [ \max_{\substack{\text{paths starting in row }0 \ \text{ending in row }n-1}} \sum_{\text{cells in the path}} grid[i][j] ]

Develop a solution that reads input from standard input (stdin) and writes the result to standard output (stdout).

inputFormat

The input starts 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 ) which represent 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.

outputFormat

For each test case, output a single line containing the maximum path sum from any cell in the first row to any cell in the last row.## sample

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

18