Minimum Energy Path

You are given a matrix of integers representing energy values. Your task is to determine the minimum energy path from any cell in the leftmost column to any cell in the rightmost column. At each step, you can move from a cell in column j to one of the three adjacent cells in column j+1 (directly right, upper-right, or lower-right).

Let \(dp[i][j]\) be the minimum energy needed to reach cell \((i,j)\). The recurrence relation is:

\(dp[i][j] = matrix[i][j] + \min \begin{cases} dp[i][j-1], \\ dp[i-1][j-1] \quad (if\ i > 0), \\ dp[i+1][j-1] \quad (if\ i < M-1) \end{cases}\)

The answer for each test case is the minimum value found in the rightmost column.

inputFormat

The input begins with 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 of the matrix. This is followed by \(M\) lines, each containing \(N\) space-separated integers, which represent the energy values in the matrix.

outputFormat

For each test case, output a single integer — the minimum energy required to travel from the leftmost column to the rightmost column. Each answer should be printed on a new line.

## sample

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

10
15
1
-2000
0

</p>