Maximum Gold Collection in a Grid

You are given a rectangular grid with \(n\) rows and \(m\) columns. Each cell in the grid contains a positive integer representing the amount of gold at that cell. Starting from any cell in the first column, you can move in one of three directions: right (\(\rightarrow\)), right-up (\(\nearrow\)), or right-down (\(\searrow\)). Your task is to determine the maximum amount of gold that can be collected when moving from the first column to the last column.

Movement rules:

• From cell \((i, j)\), you may move to \((i, j+1)\), \((i-1, j+1)\), or \((i+1, j+1)\) provided the destination cell exists within the grid.

Example:

For a grid:
1  3  3
2  1  4
0  6  4
The maximum gold collected is 12.

</p>

Use dynamic programming to solve this problem efficiently.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n m
row1
row2
...
rown
... (repeated for T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers \(n\) and \(m\) indicating the number of rows and columns in the grid.
• The next \(n\) lines each contain \(m\) space-separated integers representing the grid values.

outputFormat

For each test case, output the maximum amount of gold that can be collected on a separate line on standard output (stdout).

## sample

1
3 3
1 3 3
2 1 4
0 6 4

12

</p>