Minimum Cost Path in a Matrix

You are given a matrix of integers with r rows and c columns. Your task is to find the minimum cost path from the top-left cell to the bottom-right cell.

You can only move either right or down at any point in time. The cost of a path is the sum of all the numbers along the path.

The problem can be solved using dynamic programming. The recurrence relation is given by:

\(dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + a_{ij}\)

with the boundary conditions:

• \(dp[0][0] = a_{0,0}\)
• First row: \(dp[0][j] = dp[0][j-1] + a_{0,j}\)
• First column: \(dp[i][0] = dp[i-1][0] + a_{i,0}\)

inputFormat

The first line of input contains an integer T that denotes the number of queries. Each query begins with two integers r and c denoting the number of rows and columns of the matrix. The next r lines each contain c space-separated integers representing the matrix.

For example:

2
3 3
1 3 1
1 5 1
4 2 1
2 2
1 2
3 4

outputFormat

For each query, output the minimum cost from the top-left to the bottom-right cell on a new line.

For the input above, the output should be:

7
7

## sample

1
3 3
1 3 1
1 5 1
4 2 1

7

</p>